Pagini recente » Cod sursa (job #865956) | Cod sursa (job #2111524) | Cod sursa (job #564006) | Cod sursa (job #1578507) | Cod sursa (job #2764921)
/*
KMP
*/
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define LMAX 2000000 //doua milioane
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int nrSol;
int sol[1000 + 1];
int pref[LMAX];
char cuv[LMAX + 1];
char sir[LMAX + 1];
vector <int> solutii;
void computePref(char sir[], int N){
pref[0] = 0;
for(int i = 1; i < N; i++){
int r = pref[i - 1];
while(r != 0 && sir[r] != sir[i]){
r = pref[r - 1];
}
if(sir[r] == sir[i]){
pref[i] = r + 1;
}
else {
pref[i] = 0;
}
}
}
void KMP(char sir[], char cuv[], int lgS, int lgC){
int ct = 0;
for(int i = 0; i < lgS; i++){
while(ct != 0 && sir[i] != cuv[ct]){
ct = pref[ct - 1];
}
if(sir[i] == cuv[ct]){
ct++;
}
//else //ct = 0 daca se ajunge aici
if(ct == lgC){
nrSol++;
if(nrSol <= 1000){
sol[nrSol] = i - lgC + 1;
}
ct = pref[lgC - 1];
}
}
}
int main()
{
fin.getline(cuv, LMAX + 1);
fin.getline(sir, LMAX + 1);
int lgC = strlen(cuv);
int lgS = strlen(sir);
computePref(cuv, lgC);
KMP(sir, cuv, lgS, lgC);
fout << nrSol << "\n";
for(int i = 1; i <= nrSol; i++){
fout << sol[i] << ' ';
}
return 0;
}