Pagini recente » Cod sursa (job #948755) | Cod sursa (job #1691545) | Cod sursa (job #209827) | Cod sursa (job #1262157) | Cod sursa (job #2284346)
#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 + 1LL*(a[i]-'A'+1)*p)%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 = 19999999993, m2 = 6660133793;
long long int ha = h1(2, m1, l1, a, p1);
long long int ha2 = h1(3, m2, l1,a, p2);
long long int hs1 = h1(2, m1, l1, b, p1), hs2 = h1(3, m2, l1, b, p2);
p1/=2;
p2/=3;
if(ha == hs1 && ha2 == hs2)
{
c[o++] = 0;
}
for(int i=l1; i<l2; i++)
{
hs1 = (((hs1-(b[i-l1]-'A'+1)*p1 + m1)*2)%m1 + (b[i]-'A'+1))%m1;
hs2 = (((hs2-(b[i-l1]-'A'+1)*p2 + m2)*3)%m2 + (b[i]-'A'+1))%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;
}