Pagini recente » Cod sursa (job #2455385) | Cod sursa (job #382890) | Cod sursa (job #99844) | Cod sursa (job #2087831) | Cod sursa (job #2284395)
#include <fstream>
#include <cstring>
using namespace std;
char a[2000001], b[2000001];
int c[1002], o;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long int p1, p2;
int h1(int n, int m, int l, char a[], long long int &p)
{
int rez = 0;
p = 1;
for(int i=l-1; i>=0; i--)
{
rez = (rez + (a[i]*p)%m)%m;
p = (p * n)%m;
}
return rez;
}
int main()
{
f>>a;
f.get();
f>>b;
int l1 = strlen(a), l2 = strlen(b);
long long int m1 = 40099, m2 = 319993;
long long int ha = h1(31, m1, l1, a, p1);
long long int ha2 = h1(53, m2, l1,a, p2);
long long int hs1 = h1(31, m1, l1, b, p1), hs2 = h1(53, m2, l1, b, p2);
p1/=31;
p2/=53;
if(ha == hs1 && ha2 == hs2)
{
c[o++] = 0;
}
for(int i=l1; i<l2; i++)
{
hs1 = (((hs1-((b[i-l1])*p1)%m1 + m1)*31)%m1 + b[i])%m1;
hs2 = (((hs2-((b[i-l1])*p2)%m2 + m2)*53)%m2 + b[i])%m2;
if(ha == hs1 && ha2 == hs2)
{
if(o < 1000)
c[o] = i-l1+1;
o++;
}
}
g<<o<<"\n";
if(o > 999)
for(int i=0; i<1000; i++)
g<<c[i]<<" ";
else for(int i=0; i<o; i++)
g<<c[i]<<" ";
return 0;
}