2015ACM-ICPC亚洲区域赛沈阳站 B：Bazinga（KMP+剪枝）

March 16, 2016

题目链接

题意：给定 n 个字符串，标号 1~n，找出标号最大的字符串 i，使 1~i 中存在一个字符串不是 i 的子串。

很容易想到 KMP，如果直接搞会超时，那么可以从头开始遍历主串，记录满足条件的串，最后从后找第一个满足条件的就可以。

每次遍历子串时，如果找到字符串 j 是 i 的子串，就把 j 标记一下，再往后就不需要对 j 进行 KMP。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;

int nextt[505][2005];
char s[505][2005];
int f[505]; //f[i]=1表示i是后面某个串的子串
int ans[505]; //如果字符串i满足题意则ans[i]=1，最后从大到小遍历i即可

void kmp_pre(char x[],int m,int nextt[]){
    int i, j;
    j = nextt[0] = -1;
    i = 0;
    while(i < m){
        while(-1!=j && x[i]!=x[j])
            j = nextt[j];
        nextt[++i] = ++j;
    }
}

int KMP_Index(char x[], int m, char y[], int n, int k){
    int i = 0, j = 0;
    //kmp_pre(x, m, nextt);
    while(i < n && j < m){
        if(j == -1 || y[i] == x[j]){
            i++; j++;
        }
        else
            j = nextt[k][j];
    }
    if(j == m)
        return i-m;
    else
        return -1;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    for(int cas = 1; cas <= t; cas++){
        memset(f, 0, sizeof(f));
        memset(ans, 0, sizeof(ans));
        int n;
        scanf("%d", &n);
        //求next
        for(int i = 0; i < n; i++){
            scanf("%s", s[i]);
            kmp_pre(s[i], strlen(s[i]), nextt[i]);
        }
        int flag = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(!f[j]){
                    int k = KMP_Index(s[j], strlen(s[j]), s[i], strlen(s[i]), j);
                    if(k!=-1) f[j] = 1;
                    else{
                        flag = 1;
                    }
                }
            }
            if(flag){
                ans[i] = 1;
                flag = 0;
            }
        }
        for(int i = n-1; i >= 0; i--){
            if(ans[i]){
                printf("Case #%d: %d\n", cas, ++i);
                break;
            }
            if(i==0) printf("Case #%d: -1\n", cas);
        }

    }
    return 0;
}