Pagini recente » Cod sursa (job #1441537) | Cod sursa (job #2403199) | Cod sursa (job #3287016) | Rating UTI Gheorghita Gilca Nutu (UTI_Cozma_Nutu) | Cod sursa (job #3148008)
#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;
}
/*
longestPrefix[i] = longest prefix of the pattern that is a suffix of text[0..i].
*/