CH5702 Count The Repetitions[倍增dp]

---

这个博客貌似鸽了许久了。。

可以想到朴素算法，就是拿第二个串去暴力匹配第一个串，第一个串匹配完了后面再补，直到补到其制限次数。或者用序列自动机？循环串循环次数太多了2333。

可以看出，朴素算法中的一步一步匹配显然效率低下，考虑可不可以向后匹配一次就跳很多格？先处理出原串每个字符和模式串对应上之后向后再匹配1个字符跳的步数，然后由于循环节不大，用倍增优化即可。

$f[i][j][k]$表示文本串第$i$位和模式串第$j$位对应，然后向后匹配成功了$2^k$个字符后跳到文本串什么位置（取模），$g[i][j][k]$表示产生这种行为后文本串会被向后拓展多少次。

设$i'=f[i][j][k-1],j'=(j 2^{k-1}-1)mod$  $len_{s2} 1$

则转移为$f[i][j][k-1]=f[i'][j'][k-1]$，$g[i][j][k]=g[i][j][k-1] g[i'][j'][k-1]$。

事实上设两种状态表示麻烦了，完全可以用f表示匹配若干2次幂字符后跳到文本串拓展后的哪一位，反正循环次数再多下标也只在int范围内，g数组就可以直接不求而利用f得知了。

最后开始匹配，枚举指数，拼凑最多可以跳多少次，除以$len_{s2}$出答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define _dbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10 (c&15),c=getchar();return f?x=-x:x;
}
const int N=100 5,LOG=30;
vector<int> pos[128];
int f[N][N][LOG],g[N][N][LOG],p[LOG];
char a[N],b[N];
int n1,n2,len1,len2,m,cnt,ans;
inline void calc_pow(){for(register int i=0;i<=27;  i)p[i]=(1<<i)%len2;}
inline void Reset(){
    for(register int i='a';i<='z';  i)pos[i].clear();
    memset(f,0,sizeof f),memset(g,0,sizeof g);
}
inline char preprocess(){
    int k,l;
    for(register int i=1;i<=len1;  i)pos[a[i]].push_back((int)i);
    for(register int i=1;i<=len2;  i)if(pos[b[i]].empty())return 1;
    for(register int j=1;j<=len2;  j)
        for(register int x=0,i=pos[b[j]][0];x<(int)pos[b[j]].size();  x,i=pos[b[j]][x]){
            (k=j 1)>len2?k=1:k;
            if(*--pos[b[k]].end()<=i)l=pos[b[k]][0];else l=*upper_bound(pos[b[k]].begin(),pos[b[k]].end(),(int)i);
            f[i][j][0]=l,g[i][j][0]=l<=i;
        }
    calc_pow();
    for(register int k=1;k<=m;  k)
        for(register int j=1;j<=len2;  j)
            for(register int x=0,i=pos[b[j]][0];x<(int)pos[b[j]].size();  x,i=pos[b[j]][x])
                if(f[i][j][0]){
                    int i0=f[i][j][k-1],j0=j p[k-1]-1;j0>=len2&&(j0-=len2);  j0;
                    f[i][j][k]=f[i0][j0][k-1],g[i][j][k]=g[i][j][k-1] g[i0][j0][k-1];
                }
    return 0;
}

int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
    while(~scanf("%s%d",b 1,&n2)){
        scanf("%s%d",a 1,&n1);
        len1=strlen(a 1),len2=strlen(b 1);
        m=__lg(n1*len1);Reset();
        if(preprocess()){printf("0\n");continue;}
        int x=pos[b[1]][0],y=1;cnt=1,ans=1;
        for(register int i=m;~i;--i){
            if(cnt g[x][y][i]<=n1){
                cnt =g[x][y][i],ans =(1<<i);
                x=f[x][y][i];
                y =p[i]-1;y>=len2&&(y-=len2);  y;
            }
        }
        printf("%d\n",ans/len2/n2);
    }
    return 0;
}

等一下。。貌似我傻掉了。状态我并没有简化。还可以进行最适化。将f改为$f[i][k]$表示从$i$开始匹配模式串（不管$i$自己有没有匹配上，简化了我原来强制要与$j$对应开始匹配的条件），至少匹配多少个字符才可以匹配出$2^k$个模式串。这样暴力预处理匹配单串之后，进行转移。空间和时间上都省了很多很多。→参考lyd书。果然菜是原罪。QwQ