Pagini recente » Arhiva de probleme | Cod sursa (job #1652232) | Cod sursa (job #2847575) | Cod sursa (job #3291382) | Cod sursa (job #3148009)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, i, j, ind, nrSol;
string text, pattern;
vector<int> positions;
int main() {
fin >> pattern;
fin >> text;
n = pattern.size();
//text = " " + text;
m = text.size();
vector<int> longestPrefix(n, 0);
ind = 0;
for (i = 1; i < n; i++) {
while (ind != 0 && pattern[ind] != pattern[i]) {
ind = longestPrefix[ind - 1];
}
if (pattern[ind] == pattern[i])
ind++;
longestPrefix[i] = ind;
}
ind = 0;
for (i = 0; i < m; i++) {
while (ind != 0 && pattern[ind] != text[i]) {
ind = longestPrefix[ind - 1];
}
if (pattern[ind] == text[i])
ind++;
if (ind == n) {
nrSol++;
if (nrSol <= 1000)
positions.push_back(i - n + 1);
}
}
fout << nrSol << '\n';
for (i = 0; i < positions.size(); i++)
fout << positions[i] << " ";
fin.close();
fout.close();
return 0;
}
/*
KMP implementation.
longestPrefix[i] = longest prefix of the pattern that is a suffix of text[0..i].
Notice how this function is computed only on the pattern. Based on these values,
we determine the longest prefix of the pattern occuring as suffix at each
position in the text.
*/