Pagini recente » Cod sursa (job #155271) | Cod sursa (job #900965) | Cod sursa (job #1646679) | Cod sursa (job #1744584) | Cod sursa (job #3041828)
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
const int B1=27,B2=29,MOD1=10007,MOD2=666013 ;
string a,b ;
vector <int> pos ;
int main()
{
fin>>a>>b ;
int p1=1,p2=1,v1=0,v2=0,h1=0,h2=0 ;
for(int i=0; i<a.size(); ++i)
{
v1=(v1*B1+a[i])%MOD1 ;
v2=(v2*B2+a[i])%MOD2 ;
if(i!=0) p1=(p1*B1)%MOD1,p2=(p2*B2)%MOD2 ;
}
for(int i=0; i<a.size(); ++i)
{
h1=(h1*B1+b[i])%MOD1 ;
h2=(h2*B2+b[i])%MOD2 ;
}
if(v1==h1 && h2==v2) pos.push_back(0) ;
for(int i=a.size(); i<b.size(); ++i)
{
h1=((h1-(b[i-a.size()]*p1)%MOD1+MOD1)*B1+b[i])%MOD1 ;
h2=((h2-(b[i-a.size()]*p2)%MOD2+MOD2)*B2+b[i])%MOD2 ;
if(h1==v1 && h2==v2) pos.push_back(i-a.size()+1) ;
}
fout<<pos.size()<<'\n' ;
for(int i=0;i<min((int)pos.size(),1000);++i) fout<<pos[i]<<" " ;
return 0 ;
}