Pagini recente » Cod sursa (job #976259) | Cod sursa (job #1205424) | Cod sursa (job #2370153) | Cod sursa (job #1691508) | Cod sursa (job #2763067)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char a[2000005],b[2000005];
const int X=37;
const int MOD=1000007;
vector <int> v;
void citeste()
{
in>>a;
in>>b;
}
void solve()
{
int n=strlen(a),m=strlen(b);
int hA=0,hB=0,p=1;
for(int i=0;i<n;i++)
{
hA = (hA * X + (a[i] - 'A')) % MOD;
}
if(n>m)
{
out<<0;
return;
}
for(int i=0;i<n;i++)
{
hB = (hB * X + (b[i] - 'A')) % MOD;
}
for(int i=1;i<=n-1;i++)
p*=X;
if(hB==hA)
{
v.push_back(n);
}
for(int i=n;i<m;i++)
{
hB = ((hB - ((p * (b[i-n] - 'A')) % MOD) + MOD) * X + (b[i] - 'A')) % MOD;
if(hB==hA)
v.push_back(i-n+1);
}
out<<v.size()<<'\n';
for(int i=0;i<v.size() && i<1000;i++)
out<<v[i]<<" ";
}
int main()
{
citeste();
solve();
return 0;
}