Pagini recente » Cod sursa (job #562102) | Cod sursa (job #96811) | Cod sursa (job #375661) | Cod sursa (job #1325606) | Cod sursa (job #3153660)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
#define ll long long
const int MOD1=666013,MOD2=10027,baza=73 ;
string a,b ;
ll hashA1,hashA2,aux1=1,aux2=1,h1,h2 ;
vector <int> ans ;
int main()
{
fin>>a>>b ;
for (int i = 0; i < a.size(); ++i)
{
hashA1 = (hashA1 * baza + a[i]) % MOD1;
hashA2 = (hashA2 * baza + a[i]) % MOD2;
if (i != 0) aux1 = (aux1 * baza) % MOD1, aux2 = (aux2 * baza) % MOD2;
}
ll p1 = 0, p2 = 0;
for (int i = 0; i < a.size(); ++i)
{
p1 = (p1 * baza + b[i]) % MOD1;
p2 = (p2 * baza + b[i]) % MOD2;
}
if (p1 == hashA1 && p2 == hashA2) ans.push_back(0);
for(int i=a.size(); i<b.size(); ++i)
{
h1=((((h1-b[i-a.size()]*aux1)%MOD1+MOD1)%MOD1)*baza+b[i])%MOD1 ;
h2=((((h2-b[i-a.size()]*aux2)%MOD2+MOD2)%MOD2)*baza+b[i])%MOD2 ;
if(hashA1==h1 && hashA2==h2) ans.push_back(i-a.size()+1) ;
}
fout<<ans.size()<<'\n' ;
for(int i=0; i<min(1000,(int)ans.size()); ++i) fout<<ans[i]<<" ";
return 0;
}