HDU – 4763 Theme Section KMP

C - Theme Section KMP

 Source

HDU - 4763

My Solution

题意：给出一个字符串，找出一个尽可能长的子串，要求其在字符串的开头结尾中间都出现且不能有重叠。

KMP

先对主串跑出next数组，然后对于ptr = n，从nxt[n]开始，判断s.substr(nxt[ptr], n - 2*nxt[ptr])里是否出现了 s.substr(0, nxt[ptr]);如果没有则ptr = nxt[ptr]直到ptr == 0;

这里每个nxt[ptr]必有 s.substr(0, nxt[ptr]) == s.substr(n - nxt[ptr], nxt[ptr]),即前缀等于后缀，然后在中间为使用的地方找这个子串。

用nxt数组+KMP匹配可以几乎O(n)的跑出答案。

故 O(T*n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

inline bool find_substring(const string& pattern, const string& text)
{
    int n = pattern.size();
    vector nxt(n+1, 0);
    for(int i = 1, j = 0; i < n; i++){ j = i; while(j > 0){
            j = nxt[j];
            if(pattern[j] == pattern[i]){
                nxt[i + 1] = j + 1;
                break;
            }
        }
    }

    int /*tot = 0,*/ m = text.size();
    for(int i = 0, j = 0; i < m; i++){
        if(j < n && text[i] == pattern[j]){ j++; } else{ while(j > 0){
                j = nxt[j];
                if(text[i] == pattern[j]){
                    j++;
                    break;
                }
            }
        }
        if(j == n){
            return true;
        }
    }
    return false;
}
string s;
int nxt[maxn];
int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int T, ans, n, ptr, i, j;
    cin >> T;
    while(T--){
        cin >> s;
        n = s.size();
        memset(nxt, 0, sizeof nxt);
        for(i = 1, j = 0; i < n; i++){ j = i; while(j > 0){
                j = nxt[j];
                if(s[j] == s[i]){
                    nxt[i + 1] = j + 1;
                    break;
                }
            }
        }
        ptr = n; ans = 0;
        while(nxt[ptr]){
            //cout << nxt[ptr] << " ";
            if(find_substring(s.substr(0, nxt[ptr]), s.substr(nxt[ptr], n - 2*nxt[ptr]))){ans = nxt[ptr]; break;}
            ptr = nxt[ptr];
        }
        cout << ans << "n";
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx