Pagini recente » Cod sursa (job #2082812) | Cod sursa (job #2538689) | Cod sursa (job #3271907) | Cod sursa (job #3269770) | Cod sursa (job #3148003)
#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;
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].
*/