Pagini recente » Cod sursa (job #3182271) | Cod sursa (job #1334842) | Cod sursa (job #1463872) | Cod sursa (job #2301717) | Cod sursa (job #2763079)
#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 X1=37, X2=61;
const int MOD1=1000007, MOD2=666013;
vector <int> v;
void citeste()
{
in>>a;
in>>b;
}
void solve()
{
int n=strlen(a),m=strlen(b);
int hA1=0,hA2=0,hB1=0,hB2=0,p1=1,p2=1;
for(int i=0;i<n;i++)
{
hA1 = (1LL*hA1 * X1 + a[i]) % MOD1;
hA2 = (1LL*hA2 * X2 + a[i]) % MOD2;
}
if(n>m)
{
out<<0;
return;
}
for(int i=0;i<n;i++)
{
hB1 = (1LL*hB1 * X1 + b[i]) % MOD1;
hB2 = (1LL*hB2 * X2 + b[i]) % MOD2;
}
for(int i=1;i<=n-1;i++){
p1=(p1*X1)%MOD1;
p2=(p2*X2)%MOD2;
}
if(hB1==hA1 && hA2==hB2)
{
v.push_back(1);
}
for(int i=n;i<m;i++)
{
hB1 = ((hB1 - ((1LL*p1 * b[i-n]) % MOD1) + MOD1)*1LL * X1 + b[i]) % MOD1;
hB2 = ((hB2 - ((1LL*p2 * b[i-n]) % MOD2) + MOD2)*1LL * X2 + b[i]) % MOD2;
if(hB1==hA1 && hA2==hB2)
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;
}