F. 地图压缩 题解(kmp 最小循环节)

题目链接

题目思路

其实就是发现行和列不影响然后就可以求了

官方题解如下

不难发现行与列是两个独立的问题，因此只需要求出行的最短循环节的长度，再求出列的
最短循环节的长度，相乘就是答案。
以行为例，首先通过 Hash 将问题转化为一维问题。一维问题则是经典问题，对于一个长
度为 n 的字符串，长度为 d 的前缀是循环节当且仅当长度为 n − d 的前后缀相等，因此需要找
到这个字符串最长的前缀，满足该前缀也是该字符串的后缀。可以枚举所有可能的 d 然后使用
Hash O(1) 判断；也可以使用 KMP 算法求出 nxt 数组，答案即为 n − nxt[n]。
时间复杂度 O(n2 + qn)。

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn=2e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,q;
char s[maxn][maxn];
ull base=29;
ull r[maxn][maxn],h[maxn][maxn],power[maxn];
int x[3],y[3];
ull a[maxn];
int nxt[maxn];
int solve(ull *a,int n){
    for(int i=2,j=0;i<=n;i++){
        while(j&&a[i]!=a[j+1]){
            j=nxt[j];
        }
        if(a[i]==a[j+1]) j++;
        nxt[i]=j;
   }
   return n-nxt[n];
}
signed main(){
    scanf("%d%d",&n,&q);
    power[0]=1;
    for(int i=1;i<=n;i++){
        power[i]=power[i-1]*base;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf(" %c",&s[i][j]);
            r[i][j]=r[i][j-1]*base+s[i][j]-'a'+1;
            h[i][j]=h[i-1][j]*base+s[i][j]-'a'+1;
        }
    }
    while(q--){
        scanf("%d%d%d%d",&x[1],&y[1],&x[2],&y[2]);
        for(int i=x[1],j=1;i<=x[2];i++,j++){
            a[j]=r[i][y[2]]-r[i][y[1]-1]*power[y[2]-y[1]+1];
        }
        int ans1=solve(a,x[2]-x[1]+1);
        for(int i=y[1],j=1;i<=y[2];i++,j++){
            a[j]=h[x[2]][i]-h[x[1]-1][i]*power[x[2]-x[1]+1];
        }
        int ans2=solve(a,y[2]-y[1]+1);
        printf("%d
",ans1*ans2);
    }
    return 0;
}