Pagini recente » Cod sursa (job #1218548) | Cod sursa (job #2319974) | Cod sursa (job #1544841) | Cod sursa (job #2457095) | Cod sursa (job #1370135)
#include <bits/stdc++.h>
#define MOD1 10006667
#define MOD2 10009997
#define P 157
using namespace std;
int n, m;
char a[2000004], b[2000004];
int H1, H2, h1, h2, pp1, pp2;
int ans;
vector <int> sol;
void Andreea()
{
pp1=1;
pp2=1;
for(int i=1;i<n;i++)
{
pp1*=P, pp1%=MOD1;
pp2*=P, pp2%=MOD2;
}
for(int i=0;i<n;i++)
{
H1=H1*P+a[i];
H1%=MOD1;
H2=H2*P+a[i];
H2%=MOD2;
h1=h1*P+b[i];
h1%=MOD1;
h2=h2*P+b[i];
h2%=MOD2;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin>>a>>b;
n=strlen(a);
m=strlen(b);
Andreea();
for(int i=n-1;i<=m;i++)
{
if(h1==H1 && h2==H2)
{
ans++;
if(sol.size()<1000)
sol.push_back(i-n+1);
}
h1=( (h1 - pp1 * b[i-n+1]% MOD1 )* P + b[i+1] ) %MOD1;
if(h1<0) h1+=MOD1;
h2=( (h2 - pp2 * b[i-n+1]% MOD2 )* P + b[i+1] ) %MOD2;
if(h2<0) h2+=MOD2;
}
cout<<ans<<'\n';
for(int i=0;i<sol.size();i++)
cout<<sol[i]<<" \n"[i==sol.size()];
return 0;
}