Pagini recente » Cod sursa (job #840733) | Cod sursa (job #1506629) | Cod sursa (job #1791087) | Cod sursa (job #2168340) | Cod sursa (job #1274021)
#include <fstream>
#include <iostream>
using namespace std;
string p, t; // modelul care se cauta, textul in care se cauta
int lpref[20], s[20], lp, i, ns; // lungimile prefixelor
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp_table (string p) {
int i = 0, j = 0;
char c = '\0';
lpref[0] = -1; // !! ca sa se avanseze in t folosind formula (*)
while (i <= lp - 1) {
if (p[i] == c) {
lpref[i + 1] = j + 1; j++; i++;
}
else
if (j > 0)
j = lpref[j];
else {
lpref[i + 1] = 0; j = 0; i++;
}
c = p[j];
}
}
int kmp_search (string p, string t) {
int it = 0, ip = 0;
int ls = t.size(), lp = p.size();
while (it + ip <= ls - 1) { // nu t-a terminat nici unul dintre siruri
//cout << "t[it + ip] = " << t[it + ip] << ' ' << "p[ip] = " << p[ip] << '\n';
if (t[it + ip] == p[ip]) { // caracterele se potrivesc
ip++; // trecem sa comparam urmatorul caracter
//cout << "ip = " << ip << '\n';
}
else {
it += ip - lpref[ip]; // noua pozitie in sirul t (*)
//cout << "it = " << it << '\n';
if (ip > 0) {
ip = lpref[ip];
//cout << "ip = " << ip << '\n';
}
}
if (ip == lp) {
//cout << "gasit la " << it << ' ' << '\n';
ns++;
if (ns <= 1000)
s[ns] = it;
}
}
if (p[ip])
return -1;
else
return it;
}
int main () {
//p = "abcaabcabd"; lp = p.size();
p = "ABA"; lp = p.size();
t = "CABBCABABAB";
fin >> p >> t;
kmp_table(p);
/*
for (i = 1; i <= lp; i++)
cout << lpref[i];
cout << '\n';
*/
kmp_search(p, t);
fout << ns << '\n';
for (i = 1; i <= min(ns, 1000); i++)
fout << s[i] << ' ';
}