Pagini recente » Cod sursa (job #858969) | Cod sursa (job #3284963) | Cod sursa (job #858962) | Cod sursa (job #2456470) | Cod sursa (job #3298260)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int d=256;
const int mod=666013;
int h1, h2, k, rez[1005];
string s, t;
int main()
{
fin >> s >> t;
int m=s.size();
int n=t.size();
int h=1;
for (int i=0; i<m-1; i++)
h=(h*d)%mod;
for (int i=0; i<m; i++)
{
h1=(d*h1+s[i])%mod;
h2=(d*h2+t[i])%mod;
}
for (int i=0; i<=n-m; i++)
{
if (h1==h2)
{
int j;
for (j=0; j<m; j++)
{
if (t[i+j]!=s[j])
break;
}
if (j==m)
{
k++;
if (k<=1000)
rez[k]=i;
}
}
if (i<n-m)
{
h2=(d*(h2-t[i]*h)+t[i+m])%mod;
if (h2<0)
h2+=mod;
}
}
fout << k << '\n';
for (int i=1; i<=k; i++)
fout << rez[i] << ' ';
return 0;
}