Pagini recente » Cod sursa (job #1345143) | Cod sursa (job #674162) | Cod sursa (job #2537530) | Cod sursa (job #2089935) | Cod sursa (job #2043910)
#include <iostream>
#include <string>
#include <stdlib.h>
#include <fstream>
using namespace std;
bool match[2000001];
string s; string pattern;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int main()
{
fin >> pattern >> s;
int n = s.size(), m = pattern.size();
int long long hashpattern = 0;
int long long hashs = 0;
int long long firstpow = 1;
int nr = 0;
for (int i=1; i < m; i++) firstpow *= 73, firstpow %= 2000000011;
for (int i=0; i < m; i++) {
hashpattern = (hashpattern * 73 % 2000000011 + pattern[i]) % 2000000011;
}
for (int i=0; i < m; i++) {
hashs = (hashs * 73 % 2000000011 + s[i]) % 2000000011;
}
if (hashs == hashpattern) {
match[1] = 1;
nr++;
}
for (int i=m; i < n; i++) {
hashs = (73 * (hashs - ((int)s[i-m] * firstpow % 2000000011) % 2000000011 + 2000000011) % 2000000011 + s[i]) % 2000000011;
if (hashs == hashpattern) {
match[i-m+1] = 1;
nr++;
}
}
fout << nr << '\n';
int ap = 0;
for (int i=1; i < n && ap < 1000; i++) {
if (match[i]) {
fout << i << ' ';
ap++;
}
}
return 0;
}