Pagini recente » Cod sursa (job #1059046) | Cod sursa (job #619333) | Cod sursa (job #619328) | Cod sursa (job #1111816) | Cod sursa (job #824402)
Cod sursa(job #824402)
#include<cstdio>
#include<malloc.h>
#include<cstring>
#include<vector>
#define baza 123
#define modulo1 1000003
#define modulo2 1000033
using namespace std;
int main()
{
int baseHash1 = 0, currentHash1 = 0, baseHash2 = 0, currentHash2 = 0;
int n, m;
int P1, P2;
int ok = 1;
vector<int> matches;
char *a = new char[2000010];
char *b = new char[2000010];
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", a, b);
n = strlen(b);
m = strlen(a);
for(int i = 0; i < m; i++)
{
if(i > 0)
{
P1 = (P1 * baza) % modulo1;
P2 = (P2 * baza) % modulo2;
}
else
{
P1 = 1;
P2 = 1;
}
baseHash1 = (baseHash1 * baza + a[i]) % modulo1;
baseHash2 = (baseHash2 * baza + a[i]) % modulo2;
currentHash1 = (currentHash1 * baza + b[i]) % modulo1;
currentHash2 = (currentHash2 * baza + b[i]) % modulo2;
}
if(currentHash1 == baseHash1 && currentHash2 == baseHash2)
matches.push_back(0);
for(int i = m; i < n && ok; i++)
{
currentHash1 = ((currentHash1 - P1 * b[i - m] % modulo1 + modulo1) * baza + b[i]) % modulo1;
currentHash2 = ((currentHash2 - P2 * b[i - m] % modulo2 + modulo2) * baza + b[i]) % modulo2;
if(currentHash1 == baseHash1 && currentHash2 == baseHash2)
if(matches.size() < 1000)
matches.push_back(i - m + 1);
else
ok = 0;
}
printf("%d\n", matches.size());
for(vector<int>::iterator i = matches.begin(); i < matches.end(); i++)
printf("%d ", *i);
puts("");
return 0;
}