vijos-1382 寻找主人
寻找 vijos
2023-09-14 09:08:58 时间
题意:
给出两个同样长度的数字串;
求两个串是否本质同样。同样则输出最小表示。
长度L似乎给的不正确,大概是2000000左右吧;
题解:
最小表示法裸题。证明正确性啥的详见论文吧;
这东西大体的思路就是两个指针扫。
同样则累加k,不同就向后跳k+1个。
由于前面那段同样所以就能够由还有一个指针去扫,来节约时间。
O(n)这个非常显然咯。就一个for循环(笑)。
而且每一个数都在+++不像kmp还会由next数组回退。
模板别敲错,更别忘了。。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #define N 2100000 using namespace std; char a[N<<1],b[N<<1]; int len; int slove(char *s) { int i,j,k,cmp; for(i=1,j=2,k=0;i<=len&&j<=len&&k<=len;) { cmp=s[i+k]-s[j+k]; if(!cmp) k++; else { if(cmp>0) i+=k+1; else j+=k+1; if(i==j) j++; k=0; } } return min(i,j); } int main() { int i,j,k,s1,s2; scanf("%s%s",a+1,b+1); len=strlen(a+1); memcpy(a+len+1,a+1,sizeof(int)*len); memcpy(b+len+1,b+1,sizeof(int)*len); s1=slove(a); s2=slove(b); for(i=s1,j=s2,k=1;i<s1+len;i++,j++) if(a[i]!=b[j]) k=0; if(!k) puts("No"); else { puts("Yes"); a[s1+len]='\0'; puts(a+s1); } return 0; }