「abc135」Strings of Eternity

Source

abc135

Hint

请先思考后再展开

同余最长路
或者像我一样思考一些奇奇怪怪的做法

Solution

请先思考后再展开

设函数kmp(n,m)=k表示长为n的A与长为m的B匹配,最长出现连续k次B
先判断出,kmp(nn,m)>0的nn,讨论n与m的大小关系计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N=1e7+10;
void pre(int m) xxxx
int kmp(int n,int m) xxxx
void main()
{
scanf("%s%s",A+1,B+1);int n=strlen(A+1),m=strlen(B+1);
for(int i=n+1;i<N;i++) A[i]=A[(i-1)%n+1];
for(int i=m+1;i<N;i++) B[i]=B[(i-1)%m+1];pre(N-1);

int k=max(ceil(1.0*m/n),2.0),nn=n*k,gg=kmp(nn,m);
if(gg==0) {puts("0");return;}
int qq=kmp(nn*3,m),pp=kmp(nn*4,m);
if(pp!=qq) puts("-1");
else write(pp);
}

事实证明,这个做法不是特别显然
比较人类思维然而没想到的做法是,找到每个能匹配的位置,连向(p+t)%n
然后如果是dag就是最长路

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6068.html
转载请注明出处,谢谢!