Pagini recente » Cod sursa (job #2411266) | Cod sursa (job #1587510) | Cod sursa (job #2064070) | Cod sursa (job #585765) | Cod sursa (job #3144410)
#include <bits/stdc++.h>
#define NMAX 2000005
#define P 130
#define MOD1 100001
#define MOD2 100027
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int vA1, vA2, vB1, vB2;
int P1 = 1, P2 = 1;
int nr;
char A[NMAX], B[NMAX];
bool p[NMAX];
int main()
{
f.getline(A, NMAX);
f.getline(B, NMAX);
int na = strlen(A), nb = strlen(B);
if(na > nb)
{
g << 0;
return 0;
}
for(int i = 0; i < na; i ++)
{
if(i != 0)
{
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
vA1 = ( (vA1 * P) % MOD1 + A[i] ) % MOD1;
vA2 = ( (vA2 * P) % MOD2 + A[i] ) % MOD2;
}
for(int i = 0; i < na; i ++)
{
vB1 = ( (vB1 * P) % MOD1 + B[i] ) % MOD1;
vB2 = ( (vB2 * P) % MOD2 + B[i] ) % MOD2;
}
if(vA1 == vB1 && vA2 == vB2)
{
nr ++;
p[0] = 1;
}
for(int i = na; i < nb; i ++)
{
vB1 = ( ( vB1 - (B[i - na] * P1) % MOD1 + MOD1 ) * P + B[i] ) % MOD1;
vB2 = ( ( vB2 - (B[i - na] * P2) % MOD2 + MOD2 ) * P + B[i] ) % MOD2;
if(vA1 == vB1 && vA2 == vB2)
{
nr ++;
p[i - na + 1] = 1;
}
}
g << nr << '\n';
int val = 0;
for(int i = 0; val != nr && val != 1000; i ++)
if(p[i] == 1)
{
val ++;
g << i << " ";
}
return 0;
}