Pagini recente » Cod sursa (job #2642598) | Cod sursa (job #1435832) | Cod sursa (job #1753386) | Cod sursa (job #341997) | Cod sursa (job #342729)
Cod sursa(job #342729)
//Implementation of Knuth-Morris-Prat Algorithm
//Input s1,s2
//Output first position of s2 in s1
/*
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <string>
using namespace std;
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long T[2100000];
char s1[2100000],s2[2100000];
int matches[1024];
long cntmatch;
int M,N;
void make_table() {
T[0] = -1;
T[1] = 0;
int pos = 2,cnd = 0;
while (pos < M) {
if (s2[pos - 1] == s2[cnd]) T[pos] = cnd + 1 , ++pos , ++cnd;
else if(cnd > 0) cnd = T[cnd];
else T[pos]=0, ++pos;
}
}
int search_string() {
int i,m;
i = m = 0;
cntmatch = 0;
while (m + i < N) {
if (s2[i] == s1[m + i]) {
++i;
if (i == M) {
if (cntmatch < 1000)
matches[cntmatch++] = m;
else
cntmatch++;
if (i > 0) i = T[i];
++m;
}
} else {
m = m + i - T[i];
if (i > 0) i = T[i];
}
}
return N;
}
inline bool isalphachar(char c) {
return (((c >= 'A') && (c <= 'Z')) || ((c >= 'a') && (c <= 'z')) || ((c>='0') && (c<='9')));
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s2,sizeof(s2),stdin);
fgets(s1,sizeof(s1),stdin);
M = 0;
N = 0;
for (;isalphachar(s2[M]);++M);
for (;isalphachar(s1[N]);++N);
make_table();
search_string();
printf("%ld\n",cntmatch);
int k = (cntmatch > 1000) ? 1000 : cntmatch;
for (int i=0;i<k;++i) printf("%ld ",matches[i]);
fclose(stdin);
fclose(stdout);
return 0;
}