Pagini recente » Cod sursa (job #2865753) | Cod sursa (job #1911057) | Cod sursa (job #1314227) | Cod sursa (job #45277) | Cod sursa (job #2442499)
#include <bits/stdc++.h>
using namespace std;
const int mod1=1e9+7;
const int mod2=666013;
vector<int>v;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a,b;
cin>>a>>b;
int p1=0,p2=0,pb1=0,pb2=0,la=a.size(),p1001=1,p1002=1;
for(int i=1;i<la;i++)
p1001=(p1001*100)%mod1;
for(int i=1;i<la;i++)
p1002=(p1002*100)%mod2;
for(int i=0;i<a.size();i++)
{
p1=(p1*100+(a[i]-'A'))%mod1;
p2=(p2*100+(a[i]-'A'))%mod2;
}
for(int i=0;i<la;i++)
{
pb1=(pb1*100+(b[i]-'A'))%mod1;
pb2=(pb2*100+(b[i]-'A'))%mod2;
}
if(p1==pb1 and p2==pb2)
v.push_back(0);
for(int i=la;i<b.size();i++)
{
pb1=(pb1-(b[i-la]-'A')*p1001+mod1)%mod1;
pb1=(pb1*100+(b[i]-'A')+2*mod1)%mod1;
pb2=(pb2-(b[i-la]-'A')*p1002+mod2)%mod2;
pb2=(pb2*100+(b[i]-'A')+2*mod2)%mod2;
if(p1==pb1 and p2==pb2)
v.push_back(i-la+1);
}
cout<<v.size()<<"\n";
for(int i=0;i<min(1000,(int)v.size());i++)
cout<<v[i]<<" ";
return 0;
}