Pagini recente » Cod sursa (job #1790078) | Cod sursa (job #2494305) | Cod sursa (job #2544133) | Cod sursa (job #125268) | Cod sursa (job #3153665)
#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 ;
}
for(int i=0; i<a.size(); ++i)
{
h1=(h2*baza+b[i])%MOD1 ;
h2=(h2*baza+b[i])%MOD2 ;
}
if(hashA1==h1 && hashA2==h2) ans.push_back(0) ;
for (int i = a.size(); i < b.size(); ++i)
{
h1 = ((((h1 - aux1 * b[i - a.size()]) % MOD1) + MOD1) * baza + b[i]) % MOD1;
h2 = ((((h2 - aux2 * b[i - a.size()]) % 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;
}