Pagini recente » Cod sursa (job #1825331) | Cod sursa (job #1566006) | Cod sursa (job #493003) | Cod sursa (job #202531) | Cod sursa (job #1500740)
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector <int> KmpPrefix(string strS) {
vector <int> prefix(strS.size(), 0);
for (int i = 2, k = 0; i < strS.size(); i++) {
for (; k && strS[i] != strS[k + 1]; k = prefix[k]);
if (strS[i] == strS[k + 1])
k++;
prefix[i] = k;
}
return prefix;
}
vector <int> KMP(string strMare, string strMic, vector <int> prefix) {
vector <int> solutions;
for (int i = 1, k = 0; i < strMare.size(); i++) {
for (; k && strMare[i] != strMic[k + 1]; k = prefix[k]);
if (strMare[i] == strMic[k + 1])
k++;
if (k == strMic.size() - 1) {
solutions.push_back(i - k);
k = prefix[k];
}
}
return solutions;
}
int main() {
ifstream cin("strmatch.in");
freopen("strmatch.out", "w", stdout);
string strS, strB;
cin >> strS;
cin >> strB;
strS = " " + strS;
strB = " " + strB;
vector <int> sol = KMP(strB, strS, KmpPrefix(strS));
printf("%d\n", sol.size());
for (int i = 0; i < min(1000, (int) sol.size()); i++)
printf("%d ", sol[i]);
return 0;
}