647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/

Palindromic Substrings - LeetCode

문제

문자열에서 회문을 찾아라.

 

int dp[1010][1010] = { 0 };
int countSubstring(string s) {
    int ans = 0;
    // 한글자 처리
    for (int i = 0; i < s.size(); ++i) {
        dp[i][i] = 1;
        ans++;
    }
    // 두글자 처리
    for (int i = 0; i < s.size() - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
            ans++;
        }
    }

    // 세글자 이상부터
    for (int sz = 3; sz <= s.size(); ++sz) {
        for (int i = 0; i < s.size(); ++i) {
            int begin = i;
            int end = i + sz - 1;
            if (end >= s.size()) continue;
            if (dp[begin + 1][end - 1] == 1 && (s[begin] == s[end])) {
                dp[begin][end] = 1;
                ans++;
            }
        }
    }
    // 최초 회문이 있는 인덱스를 리턴하려면 어떻게 할까요?
    int sol = 0;
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < s.size(); j++) {
            if (dp[i][j]) {
                //cout << dp[i][j] << endl;
                return i;
                //return s[i];
            }
        }
    }

    // 가장 긴 회문을 구하시오? 반환값 시작지점인지, 문자열인지 구체적인 질문
    // 크기를 반환할 것인가?

    // 가장큰 길이를 구하시오

    int sol = 0;
    for (int left = 0; left < s.size(); ++left)
        for (int right = left; right < s.size(); ++right) {
            int sz = right - left + 1;
            if (dp[left][right] == 1)
                sol = max(sol, sz);
        }

    return ans;
}
// O(n^2)
// 개선된 알고리즘 manacher

 

https://velog.io/@jjj7061/Manachers-Algorithm

Manacher's Algorithm