HDU 5510 Bazinga KMP

题意：

给\(n(1 \leq n \leq 500)\)个字符串，求一个最大的\(i\)，使得存在一个\(S_{j}\)不是\(S_i\)的子串。

分析：

维护两个指针\(l,r\)

那么有两种情况：

如果\(S_l\)是\(S_r\)的子串，那么\(l\)++。
如果\(S_l\)不是是\(S_r\)的子串，那么将答案更新为\(r\)，然后\(r\)++。

考虑\(S_{r+1}\)的时候为什么同样不考虑\(S_l\)之前的串了呢？

因为\(S_l\)之前的串都是后面某个串的子串，所以如果他们中有不是\(S_{r+1}\)子串的串的话，那么一定有对应的那个串也不是\(S_{r+1}\)的子串。这样保证\(r\)一定能更新到\(ans\)。

因此降了一维的复杂度。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 500 + 5;

const int maxl = 2000 + 5;

int f[maxl];

char s[maxn][maxl];

void getFail(char* s) {

    f[0] = f[1] = 0;

    for(int i = 1; s[i]; i++) {

        int j = f[i];

        while(j && s[i] != s[j]) j = f[j];

        f[i+1] = s[i] == s[j] ? j+1 : 0;

    }

}

bool match(char* T, char* P) {

    int n = strlen(T), m = strlen(P);

    getFail(P);

    int j = 0;

    for(int i = 0; i < n; i++) {

        while(j && P[j] != T[i]) j = f[j];

        if(P[j] == T[i]) j++;

        if(j == m) return true;

    }

    return false;

}

int main()

{

    int T; scanf("%d", &T);

    for(int kase = 1; kase <= T; kase++) {

        int n; scanf("%d", &n);

        for(int i = 1; i <= n; i++) scanf("%s", s[i]);

        int L = 1, R, ans = -1;

        for(R = 2; R <= n; R++) {

            while(L < R) {

                if(match(s[R], s[L])) L++;

                else {

                    ans = R;

                    break;

                }

            }

        }

        printf("Case #%d: %d\n", kase, ans);

    }

    return 0;

}

巴特西

HDU 5510 Bazinga KMP

题意：

分析：

最新文章

热门文章