Pagini recente » Cod sursa (job #419064) | Cod sursa (job #1796064) | Cod sursa (job #606937) | Autentificare | Cod sursa (job #1550169)
#include <fstream>
#include <cstring>
#define P 67
#define p1 666013
#define p2 666017
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000001], B[2000001];
int a1,a2,d1=1,d2=1,m,n,i,nr,b1,b2,c;
char q[2000001];
int main()
{
f.getline(A,2000000);
f.getline(B,2000000);
m=strlen(A);
n=strlen(B);
for (i=0;i<m;i++)
{
a1=(a1 *P+A[i])%p1;
a2=(a2 *P+ A[i])%p2;
if (i != 0)
d1=(d1*P)%p1,
d2=(d2*P)%p2;
}
for (i=0;i < m; i++)
b1 =(b1 * P + B[i]) % p1,
b2 =(b2 * P + B[i]) % p2;
if (b1 == a1 && b2 == a2)
q[0] = 1, nr++;
for (i = m; i < n; i++)
{
b1 = ((b1 - (B[i - m] * d1) % p1 + p1) * P + B[i]) % p1;
b2 = ((b2 - (B[i - m] * d2) % p2 + p2) * P + B[i]) % p2;
if (b1 == a1 && b2 == a2)
q[ i - m + 1 ] = 1, nr++;
}
g<<nr<<'\n';
for (i = 0; i < n && c < 1000; i++)
if (q[i])
{c++;
g<<i<<" ";}
return 0;
}