Pagini recente » Cod sursa (job #1818248) | Cod sursa (job #2021102) | Cod sursa (job #2222868)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define NMAX 2000001
#define PRIM1 48487
#define PRIM2 59197
using namespace std;
int hash1, hash2;
char a[NMAX], b[NMAX];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", &a);
scanf("%s", &b);
int sizeA = strlen(a);
for(int i = 0; i < sizeA; ++i)
{
hash1 = (hash1 + a[i]) % PRIM1;
hash2 = (hash2 + a[i]) % PRIM2;
}
int bHash1 = 0;
int bHash2 = 0;
for(int i = 0; i < sizeA - 1; ++i)
{
bHash1 = (bHash1 + b[i]) % PRIM1;
bHash2 = (bHash2 + b[i]) % PRIM2;
}
vector<int> ans;
for(int i = sizeA - 1; b[i] != NULL; ++i)
{
bHash1 = (bHash1 + b[i]) % PRIM1;
bHash2 = (bHash2 + b[i]) % PRIM2;
int beginPos = i - sizeA + 1;
if(hash1 == bHash1 && hash2 == bHash2)
{
int ok = 1;
for(int j = beginPos; j <= i; ++j)
{
if(a[j - beginPos] != b[j])
{
ok = 0;
break;
}
}
if(ok)
{
ans.push_back(beginPos);
}
}
bHash1 = (bHash1 - b[beginPos] + PRIM1) % PRIM1;
bHash2 = (bHash2 - b[beginPos] + PRIM2) % PRIM2;
}
printf("%d\n", ans.size());
for(int i = 0; i < ans.size() && i < 1000; ++i)
printf("%d ", ans[i]);
return 0;
}