Pagini recente » Cod sursa (job #3356336) | Cod sursa (job #3343291) | Cod sursa (job #3356711) | Cod sursa (job #3356405) | Cod sursa (job #2671335)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lpsG[2000005];
int nrRez;
vector<int> rez;
void ComputeLPSArray(char* pat, int M, int* lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0)
len = lps[len - 1];
else {
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);
ComputeLPSArray(pat, M, lpsG);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
i++;
j++;
}
if (j == M) {
j = lpsG[j - 1];
nrRez++;
rez.push_back(i - j);
}
else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lpsG[j - 1];
else
i++;
}
}
}
char pat[200005];
char txt[200005];
int main() {
fin >> pat >> txt;
KMPSearch(pat, txt);
fout << nrRez << "\n";
for (int i = 0; i < rez.size(); ++i)
fout << rez[i] - 2 << " ";
return 0;
}