UOJ #5.[NOI2014]动物园

序言

  这个题写的我好迷啊==

题目简述

  园长想让你求一个字符串的”不互相重叠的公共前后缀个数”然后再乘起来.一大骡子的字,总结一下就是这个意思.

解析

  如果你不会$KMP$….那我也没办法(笑)
  我们知道,$next$保存的是有重叠部分的最大长度.那么我们在它计算的过程中,把当前$next[i]$的位置,存一个长度$cnt[i]$,啥意思?
  我$next[i]$从头扫到尾,相当于一个递推得到最大长度.同时进行$cnt[i]$从头扫到尾,相当于递推得到最大个数.
  然后再用$next[]$数组,找到不重复的位置,也就是$j\leq{i/2}$这样的位置,计算$cnt$,完成.

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

typedef long long ll;

const int INF = 1e9;
const int MAXN = 2e6 + 10;

int n[MAXN],len,f[MAXN];
char t[MAXN];
void getnext(char *t)
{
    n[0] = 0,n[1]=1;
    f[0] = -1, f[1] = 0;
    for (int i = 1, j = 0; i < len; i++) {
        while (j != -1 && t[i] != t[j])
            j = f[j];
        ++j;
        f[i + 1] = j;
        n[i+1] = n[j]+1;
    }
}
const int mod = 1e9 + 7;
int main() {
    int k;
    cin >> k;
    while (k--) {
        cin >> t;
        len = strlen(t);
        getnext(t);
        ll ans = 1;
        for (int i = 1,j=0; i < len; i++) {
            while (j != -1 && t[i] != t[j])
                j = f[j];
            j++;
            while (j * 2 > i + 1)
                j = f[j];
            ans = ans * (ll)(n[j] + 1)%mod;
        }
        cout << ans << endl;
    }
    return 0;
}