洛谷 P2031 脑力达人之分割字串

题目传送门

解题思路:

f[i]表示到第i位可获得的最大分割次数,对于每个f[i]都可由其符合条件的前缀转移过来,条件就是当前串除了前缀的剩余字符里有所给单词,然后一看,这不是在剩余字符里找有没有所给单词吗?所以果断KMP,其实本题好像不用KMP,暴力模拟就可以,但是为了练习KMP装逼,所以就写一下.

AC代码:

#include<iostream>
#include<cstdio>

using namespace std;

string l,p,a[501];
int n,kmp[501][301],f[501]; 

inline int max(int s,int d) {
    if(s > d) return s;
    return d;
}

int main() {
    cin >> p;
    l = " " + p;
    scanf("%d",&n);
    for(int i = 1;i <= n; i++) {
        cin >> p;
        a[i] = " " + p;
        int len = a[i].length() - 1,k = 0;
        for(int j = 2;j <= len; j++) {
            while(k != 0 && a[i][j] != a[i][k+1]) k = kmp[i][k];
            if(a[i][j] == a[i][k+1]) k++;
            kmp[i][j] = k;
        }
    }
    for(int i = 1;i <= l.length() - 1; i++) {
        for(int j = 1;j <= i; j++) {
            string u = " " + l.substr(j,i-j+1);
            int o;
            bool vis = 0;
            for(int k = 1;k <= n; k++) {
                o = 0;
                for(int p = 1;p <= u.length() - 1; p++) {
                    while(o != 0 && u[p] != a[k][o+1]) o = kmp[k][o];
                    if(u[p] == a[k][o+1]) o++;
                    if(o == a[k].length() - 1) {
                        vis = 1;
                        break;
                    }
                }
                if(vis) break;
            }
            if(vis)
                f[i] = max(f[i],f[j-1] + 1);
        }
    }
    printf("%d",f[l.length()-1]);
    return 0;
}