Pagini recente » Cod sursa (job #1944607) | Cod sursa (job #3170601) | Cod sursa (job #149115) | Cod sursa (job #1224167) | Cod sursa (job #2981486)
#include <fstream>
using namespace std;
string m, t; // modelul care se cauta, textul in care se cauta
int lp[2000001], s[1001], lm, i, ns; // lungimile prefixelor, solutiile
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp_table(string m) {
int im = 0, ip = 0; // indice pentru model, indice pentru prefix
char c = '\0';
lp[0] = -1; // !! ca sa se avanseze in t folosind formula [*]
while (im <= lm - 1) {
if (m[im] == c) {
lp[im + 1] = ip + 1;
ip++;
im++;
}
else //
if (ip > 0)
ip = lp[ip];
else {
lp[im + 1] = 0;
ip = 0;
im++;
}
c = m[ip];
}
}
void kmp_search(string m, string t) {
int it = 0, im = 0;
int lt = t.size(), lm = m.size();
while (it + im <= lt - 1) { // cat timp nu depasim ultimul caracter
if (t[it + im] == m[im]) // Caracterele se potrivesc.
im++; // Trecem sa comparam urmatorul caracter.
else { // Caracterele nu se potrivesc.
it += im - lp[im]; // noua pozitie in text [*]
if (im > 0)
im = lp[im]; // Mergem la primul loc unde nu am comparat.
}
if (im == lm) { // S-au potrivit toate caracterele.
ns++;
if (ns <= 999)
s[++ns] = it;
}
}
}
int main() {
fin >> m >> t;
lm = m.size();
kmp_table(m);
/*
for (i = 1; i <= lm; i++)
cout << lp[i];
cout << '\n';
*/
kmp_search(m, t);
fout << ns << '\n';
for (i = 1; i <= min(ns, 1000); i++)
fout << s[i] << ' ';
}