Pagini recente » Cod sursa (job #3126105) | Cod sursa (job #164348) | Cod sursa (job #880308) | Cod sursa (job #377172) | Cod sursa (job #1563427)
#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;
int hA1, hA2, hB1, hB2, for1 = 1, for2 = 1, nr;
vector<int> ret;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", &a); n = strlen(a);
scanf("%s", &b); m = strlen(b);
if(n > m) {cout << "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);
}
}
cout << nr << "\n";
for(int i = 0; i < ret.size() && i < 1000; i ++) {
cout << ret[i] << " ";
}
cout << "\n";
return 0;
}