Pagini recente » Cod sursa (job #2069929) | Cod sursa (job #1073839) | Cod sursa (job #2777949) | Cod sursa (job #1132126) | Cod sursa (job #579260)
Cod sursa(job #579260)
#include <stdio.h>
#include <fstream>
#include <string.h>
using namespace std;
const int nmax = 2000010;
const int P = 73;
const int Mod1 = 100007;
const int Mod2 = 100021;
char A[nmax], B[nmax];
int match[nmax], NA, NB;
int hash1, hash2, T1, T2, P1, P2;
void read()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
NA = strlen(A);
NB = strlen(B);
}
void TakeOff()
{
P1 = P2 = 1;
int i;
for(i = 0; i < NA; i++)
{
T1 = ((T1 * P) % Mod1 + B[i]) % Mod1;
T2 = ((T2 * P) % Mod2 + B[i]) % Mod2;
hash1 = ((hash1 * P) % Mod1 + A[i]) % Mod1;
hash2 = ((hash2 * P) % Mod2 + A[i]) % Mod2;
if(i < NA -1 )
{
P1 = (P1 * P) % Mod1;
P2 = (P2 * P) % Mod2;
}
}
}
int Nr;
void solve()
{
if(hash1 == T1 && hash2 == T2)
match[0] = 1, Nr++;
int i;
for(i = NA; i < NB; i++)
{
T1 = ((T1 - (P1 * B[i - NA]) % Mod1 + Mod1) * P + B[i]) % Mod1;
T2 = ((T2 - (P2 * B[i - NA]) % Mod2 + Mod2) * P + B[i]) % Mod2;
if(T1 == hash1 && T2 == hash2)
match[i - NA + 1] = 1, Nr++;
}
}
void UnLoad()
{
printf("%d\n", Nr);
Nr = 0;
int i;
for(i = 0; i < NB && Nr < 1000; i++)
if(match[i])
printf("%d ", i), Nr++;
}
int main()
{
read();
if(NA > NB)
{
printf("0\n");
return 0;
}
TakeOff();
solve();
UnLoad();
return 0;
}