Pagini recente » Cod sursa (job #1723825) | Cod sursa (job #2854874) | Cod sursa (job #1972586) | Cod sursa (job #1839581) | Cod sursa (job #3204338)
#include <bits/stdc++.h>
#define mod1 666013
#define mod2 1000000007
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int rptl(int b,int e,int mod){
int rez=1;
while(e!=0){
if(e%2==0){
b=(1LL*b*b)%mod;
e/=2;
}
else
{
rez=(1LL*rez*b)%mod;
--e;
}
}
return rez;
}
int v[1001];
char s1[2000001],s2[2000001];
int main()
{
int i,l1,l2;
int val1_1,val1_2,val2_1,val2_2;
val1_1=val1_2=val2_1=val2_2=0;
in>>s1;
in>>s2;
l1=strlen(s1);
l2=strlen(s2);
int putere1=rptl(67,l1-1,mod1);
int putere2=rptl(67,l1-1,mod2);
if(l2<l1)
out<<0;
else{
int cnt=0;
for(i=0;i<l1;++i){
val1_1=(val1_1*67+s1[i])%mod1;
val1_2=(val1_2*67+s1[i])%mod2;
}
for(i=0;i<l1;++i){
val2_1=(val2_1*67+s2[i])%mod1;
val2_2=(val2_2*67+s2[i])%mod2;
}
if(val1_1==val2_1&&val1_2==val2_2){
++cnt;
v[cnt]=i-l1;
}
for(i=l1;i<=l2;++i){
val2_1=((val2_1-1LL*s2[i-l1]*putere1+mod1)*67+s2[i])%mod1;
val2_2=((val2_2-1LL*s2[i-l1]*putere2+mod2)*67+s2[i])%mod2;
if(val1_1==val2_1&&val1_2==val2_2&&cnt<1000){
++cnt;
v[cnt]=i-l1;
}
}
out<<cnt<<'\n';
for(i=1;i<=cnt;++i)
out<<v[i]+1<<" ";
}
return 0;
}