Pagini recente » Cod sursa (job #2321695) | Cod sursa (job #50039) | Cod sursa (job #24662) | Cod sursa (job #403253) | Cod sursa (job #2967505)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod1 = (1e9)+7,mod2 = (666013);
const int p1 = 61, p2 = 67;
string a,b;
long long h1,h2,z1,z2,plen = 1,p2len = 1;
vector <int> V;
int main()
{
fin>>a>>b;
int len = a.size();
int len2 = b.size();
for(int i = 1;i<len;i++)
{
plen = plen*p1%mod1;
p2len = p2len*p2%mod2;
}
for(int i = 0;i<len;i++)
{
h1 = (h1*p1 + a[i])%mod1;
h2 = (h2*p2 + a[i])%mod2;
}
for(int j = 0;j<len;j++)
{
z1 = (z1*p1 + b[j])%mod1;
z2 = (z2*p2 + b[j])%mod2;
}
if(h1 == z1 && h2 == z2)
{
V.push_back(0);
}
for(int i = len;i<len2;i++)
{
z1 -= (b[i-len]*plen)%mod1;
z2 -= (b[i-len]*p2len)%mod2;
z1 = (z1 + mod1) %mod1;
z2 = (z2 + mod2) %mod2;
z1 = (z1*p1 + b[i])%mod1;
z2 = (z2*p2 + b[i])%mod2;
if(h1==z1 && h2 == z2)
{
V.push_back(i-len+1);
}
}
fout<<V.size()<<'\n';
for(int i = 0;i<(min((int)V.size(),1000));i++)
{
fout<<V[i]<<' ';
}
}