Pagini recente » Borderou de evaluare (job #2051504) | Cod sursa (job #3239048) | Cod sursa (job #3289357) | Cod sursa (job #3279348) | Cod sursa (job #3148005)
#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;
vector<int> longestPrefix(2000001);
int main() {
fin >> pattern;
fin >> text;
n = pattern.size();
text = " " + text;
m = text.size();
ind = 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);
}
}
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].
*/