Pagini recente » Cod sursa (job #925006) | Cod sursa (job #2272881) | Cod sursa (job #1441916) | Cod sursa (job #23646) | Cod sursa (job #2498239)
// C++ program for implementation of KMP pattern searching
// algorithm
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int sol[100000],cont;
char a[2000010], b[2000010];
void PAS(char* sir1, int M, int* lps);
void KMP(char* sir1, char* sir2,int &cont,int sol[]){
int m=strlen(sir1);
int n=strlen(sir2);
int lps[m];
PAS(sir1, m, lps);
int i = 0;
int j = 0;
while (i<n) {
if (sir1[j] == sir2[i]) {
j++;
i++;
}
if (j == m) {
cont++;
sol[cont]=i-j;
j=lps[j-1];
}
else{
if(i<n&& sir1[j] != sir2[i]) {
if (j != 0){
j = lps[j - 1];
}
else{
i = i + 1;
}
}
}
}
}
void PAS(char* sir1, int M, int* lps){
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (sir1[i] == sir1[len]) {
len++;
lps[i] = len;
i++;
}
else{
if (len != 0) {
len = lps[len - 1];
}
else{
lps[i] = 0;
i++;
}
}
}
}
// Driver program to test above function
int main(){
fin>>a;
fin>>b;
KMP(a, b,cont,sol);
fout<<cont<<"\n";
for(int i=1;i<=min(cont,1000);i++){
fout<<sol[i]<<" ";
}
return 0;
}