Pagini recente » Cod sursa (job #1028159) | Cod sursa (job #2218386) | Cod sursa (job #879396) | Cod sursa (job #1012718) | Cod sursa (job #2674171)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define MAXLENGTH 2000001
char T[MAXLENGTH], P[MAXLENGTH];
int N, LPS[MAXLENGTH], result[MAXLENGTH];
int lenT, lenP;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calculateLongestPrefixSubfix() {
int i=1;
int j=0;
LPS[0] = 0;
while (i < lenP) {
if (P[i] == P[j]) {
LPS[i] = LPS[i-1] + 1;
i++;
j++;
}
else if (j != 0) {
j=LPS[j-1];
}
else {
i++;
}
}
}
void KMP() {
int i=0;
int j=0;
while (i<lenT) {
if(T[i] == P[j]) {
i++;
j++;
} else if (j != 0) {
j=LPS[j-1];
} else {
i++;
}
if (j == lenP) {
result[N] = i-j;
N++;
j = LPS[j-1];
}
}
}
void afisare() {
fout<<N<<endl;
if (N > 1000) {
N = 1000;
}
for (int i=0; i<N; i++) {
fout<<result[i]<<" ";
}
}
int main()
{
fin.getline(P, MAXLENGTH);
fin.getline(T, MAXLENGTH);
lenT = strlen(T);
lenP = strlen(P);
calculateLongestPrefixSubfix();
KMP();
afisare();
return 0;
}