Pagini recente » Cod sursa (job #1375998) | Cod sursa (job #2383736) | Cod sursa (job #2538369) | Cod sursa (job #199227) | Cod sursa (job #3148004)
#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();
m = text.size();
ind = 0;
vector<int> longestPrefix(m, 0);
if (pattern[0] == text[0]) {
longestPrefix[0] = 1;
ind = 1;
if (ind == n)
positions.push_back(0);
}
for (i = 1; i < m; i++) {
while (ind != 0 && pattern[ind] != text[i]) {
ind = longestPrefix[ind - 1];
}
if (pattern[ind] == text[i])
ind++;
longestPrefix[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;
}
/*
longestPrefix[i] = longest prefix of the pattern that is a suffix of text[0..i].
*/