P2375 [NOI2014]动物园(kmp)

电玩女神 2021-09-07 06:08 277阅读 0赞

考虑num数组与next数组的区别。

1.  如何统计数目。根据border那一套理论，s的所有border长度为 f a i l \[ n \] , f a i l \[ f a i l \[ n \] \] . . . fail\[n\],fail\[fail\[n\]\]... fail\[n\],fail\[fail\[n\]\]...。那么，我们其实可以在求next的过程中，把这个数量进行递推，就得到了一个可以重叠版的num数组。
2.  如何去掉不重合的部分。用求next时一样的方法去求num。实际过程中犯了个错误，在求next数组判断了是否超过了一半，这里不能直接判断，会对后面产生影响，解决方法是再做一遍求next的过程，去跳num数组。

*  复杂度分析：  
    每次位置指针i++时，失配指针j至多增加一次，所以jj至多增加len次，从而至多减少len次，复杂度为 O ( n ) O(n) O(n)

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define de(c) cout << #c << " = " << c << endl
    #define dd(c) cout << #c << " = " << c << " "
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    const int maxn = 1e6 + 100;
    int fa[maxn],num[maxn];
    char str[maxn];
    ll ans;
    void get_fa(int f[],char s[])
    { 
    	int n = strlen(s);
    	int j = f[0] = num[0] = 0;
    	num[1] = 1;
    	rep(i,1,n)
    	{ 
    		while(j && s[i] != s[j]) j = f[j-1];
    		j += s[i] == s[j];
    		f[i] = j;
    		num[i+1] = num[j]+1;
    	}
    
    	j = 0;
    	rep(i,1,n)
    	{ 
    		while(j && s[i] != s[j]) j = f[j-1];
    		j += s[i] == s[j];
    		while(j*2 > i+1) j = f[j-1];
    		ans = ans % mod *(num[j]+1) % mod;
    	}
    }
    int main(int argc, char const *argv[])
    { 
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{ 
    		ans = 1;
    		scanf("%s",str);
    		get_fa(fa,str);
    		printf("%lld\n",ans);
    	}
    	return 0;
    }