传送门:Justice String
题意:有两个串A,B,问是否存在A的一个子串S,S和B的长度相等,最多有2个字符不同。如果有多个,输出其实下标最小S的下标,没有输出-1。
分析:从A每个位置开始找最长公共前缀,如果最长公共前缀长度不大于lenb,继续从下一次位置开始找,至多找两次,如果一直找不到就算不存在。
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#define LL long long
#define N 100010
using namespace std;
const LL mod=1000000007ll;
const LL SEED=;
char a[N],b[N];
int lena,lenb;
unsigned LL hha[N],hhb[N];
unsigned LL p[N];
void init()
{
hha[]=a[];
hhb[]=b[];
for(int i=;i<lena;i++)
{
hha[i]=hha[i-]*SEED+a[i];
}
for(int i=;i<lenb;i++)
{
hhb[i]=hhb[i-]*SEED+b[i];
}
}
LL calc(int x,int len,unsigned LL f[])
{
return f[x+len-]-f[x-]*p[len];
}
int lcp(int pa,int pb)
{
int l=,r=lenb-pb,ans;
while(l<=r)
{
int m=(l+r)>>;
if(calc(pa,m,hha)==calc(pb,m,hhb))
l=m+,ans=m;
else r=m-;
}
return ans;
}
int main()
{
int T,cas=;
p[]=1ll;
for(int i=;i<N;i++)p[i]=p[i-]*SEED;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",a,b);
lena=strlen(a);
lenb=strlen(b);
init();
int ans=-;
for(int i=;i<=lena-lenb;i++)
{
int num=;
num+=lcp(i+num,num);
if(num>=lenb)
{
ans=i;break;
}
num++;
if(num>=lenb)
{
ans=i;break;
}
num+=lcp(i+num,num);
if(num>=lenb)
{
ans=i;break;
}
num++;
if(num>=lenb)
{
ans=i;break;
}
num+=lcp(i+num,num);
if(num>=lenb)
{
ans=i;break;
}
}
printf("Case #%d: %d\n",cas++,ans);
}
}