周期

思路

对字符串$s$自己匹配求出$next$数组，我们发现当$i-next[i]$能够整除$i$时候，那么$s[1~i-next[i]]$就是$s[i-1]$的最小循环元，至于次数那么也就是$i/(i-next[i])$。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e6+10;
int ne[tt];
char a[tt];
int n;

void solve(){
    ne[1]=0;
    for(int i=2,j=0;i<=n;i++){
        while(j>0&&a[i]!=a[j+1]){
        	j=ne[j];
		}
        if(a[j+1]==a[i]){
        	j++;
		}
        ne[i]=j;
    }
}

int main(){
	int cnt=1;
	while(cin >>n&&n!=0){
		cout <<"Test case #"<<cnt<<endl;
		cnt++;
		for(int i=1;i<=n;i++){
			cin >>a[i];
		}
        solve();
        int num=0;
        for(int i=2;i<=n;i++){
        	if(i%(i-ne[i])==0&&i/(i-ne[i])>1){
        		cout <<i<<" "<<i/(i-ne[i])<<endl;
			}
		}
        cout <<endl;
	} 
	return 0;
}

项链

思路

我们知道最终要输出最小表示法。判断是否相等时，也可以利用最小表示法。

所以思路就是比较两条字符串的最小表示法，判断一下。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int len=0;

string get(string s){
	int i=1;
	for(int j=2;i<=len&&j<=len;){
		int k=0;
		while(k<len&&s[i+k]==s[j+k]){
			k++;
		}
		if(s[i+k]>s[j+k]){
			swap(i,j);
		}
		j=j+k+1;
		if(i==j){
			j++;
		}
	}
	return s.substr(i,len);
}

signed main(){
	string a,b;
	cin >>a>>b;
	len=a.size();
	a=" "+a+a;
	b=" "+b+b;
	string ans_a,ans_b;
	ans_a=get(a);
	ans_b=get(b);
	if(ans_a==ans_b){
		cout <<"Yes"<<endl;
		cout <<ans_a;
	}else{
		cout <<"No";
	}
	return 0;
}

奶牛矩阵

思路

用$nxt$数组求$n$和$m$的最小循环节，也就是最小矩阵，就一定会覆盖住。

代码

#include<bits/stdc++.h>
using namespace std;

const int tt=1e4+10;
int n,m;
char a[tt][110],z[110][tt];
int nxt1[tt],nxt2[110];

int f(int &len){
	int i=0,j=-1;
	nxt1[0]=-1;
	while(i<len){
		if(j==-1||strcmp(a[i],a[j])==0){
			nxt1[++i]=++j;
		}else{
			j=nxt1[j];
		}
	}
	return len-nxt1[len];
}

int g(int &len){
	int i=0,j=-1;
	nxt2[0]=-1;
	while(i<len){
		if(j==-1||strcmp(z[i],z[j])==0){
			nxt2[++i]=++j;
		}else{
			j=nxt2[j];
		}
	}
	return len-nxt2[len];
}

int main(){
	int n,m;
	cin >>n>>m;
	for(int i=0;i<n;i++){
		cin >>a[i];
	}
	memset(z,'\0',sizeof(z));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			z[j][i]=a[i][j];
		}
	}
	cout <<f(n)*g(m);
	return 0;
}

匹配统计

思路

首先预处理两个串的哈希值。对于$a$字符串的每个后缀，二分其与$b$字符串的最长公共前缀的长度，并用哈希判断是否相等即可。

得出后缀数组中相邻两个后缀的最长公共前缀的长度后统计答案即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int tt=2e5+10;

char a[tt],b[tt];
int nxt[tt];
int f[tt],cnt[tt];

int main(){
	int n,m,q;
    cin >>n>>m>>q;
    scanf("%s",a+1);
    scanf("%s",b+1);
    nxt[1]=0;
    for(int i=2,j=0;i<=m;i++){
        while(j>0&&b[i]!=b[j+1]){
        	j=nxt[j];
		}
        if(b[i]==b[j+1]) j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while(j>0&&(j==m||a[i]!=b[j+1])){
        	j=nxt[j];
		}
        if(a[i]==b[j+1]){
        	j++;
		}
        f[i]=j;
    }
    for(int i=1;i<=n;i++){
        cnt[f[i]]++;
    }
    for(int i=m;i>=1;i--){
        cnt[nxt[i]]+=cnt[i];
    }
    while(q--){
        int x;
        cin >>x;
        cout <<cnt[x]-cnt[x+1]<<endl;
    }
    return 0;
}

谢谢