Pagini recente » Cod sursa (job #3224140) | Cod sursa (job #1820089) | Cod sursa (job #2180653) | Cod sursa (job #2782913) | Cod sursa (job #2038030)
#include <iostream>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <vector>
using namespace std;
vector<int> poz;
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 hashpattern = 0;
int hashs = 0;
int firstpow = 1;
int nr = 0;
for (int i=1; i < m; i++) firstpow *= 101;
for (int i=0; i < m; i++) {
hashpattern = (hashpattern * 101 + pattern[i]);
}
for (int i=0; i < m; i++) {
hashs = hashs * 101 + s[i];
}
if (hashs == hashpattern) {
poz.push_back(1);
nr++;
}
for (int i=m; i < n; i++) {
hashs = (101 * (hashs - ((int)s[i-m] * firstpow)) + s[i]);
if (hashs == hashpattern) {
if (s.compare(i-m+1, m, pattern) == 0) {
poz.push_back(i - m + 1);
nr++;
}
}
}
fout << nr << '\n';
for (int i=0; i < nr; i++) {
fout << poz[i] << ' ';
}
return 0;
}