Pagini recente » Cod sursa (job #764291) | Cod sursa (job #2958525) | Cod sursa (job #182399) | Cod sursa (job #679631) | Cod sursa (job #1563421)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define key2 100007
#define key1 100021
#define fact 101
using namespace std;
char a[2000005]; int n;
char b[2000005]; int m;
long long hA1, hA2, hB1, hB2, for1 = 1, for2 = 1; int nr;
vector<int> ret;
int main()
{
FILE *f = fopen("strmatch.in", "r");
FILE *g = fopen("strmatch.out", "w");
fscanf(f, "%s", &a); n = strlen(a);
fscanf(f, "%s", &b); m = strlen(b);
if(n > m) {fprintf(g, "0\n"); return 0;}
for(int i = 0; i < n; i ++) {
hA1 = (hA1 * fact + a[i]) % key1;
hA2 = (hA2 * fact + a[i]) % key2;
if(i) {
for1 = (for1 * fact) % key1;
for2 = (for2 * fact) % key2;
}
}
for(int i = 0; i < n; i ++) {
hB1 = (hB1 * fact + b[i]) % key1;
hB2 = (hB2 * fact + b[i]) % key2;
}
if(hA1 == hB1 && hA2 == hB2) {
nr ++;
ret.push_back(0);
}
for(int i = n; i < m; i ++) {
hB1 = ((hB1 - (b[i - n] * for1) % key1 + key1) * fact + b[i]) % key1;
hB2 = ((hB2 - (b[i - n] * for2) % key2 + key2) * fact + b[i]) % key2;
if(hA1 == hB1 && hA2 == hB2) {
nr ++;
ret.push_back(i - n + 1);
}
}
fprintf(g, "%d\n", nr);
for(int i = 0; i < ret.size() && i < 1000; i ++) {
fprintf(g, "%d ", ret[i]);
}
fprintf(g, "\n");
return 0;
}