Pagini recente » Cod sursa (job #536784) | Cod sursa (job #3128316) | Cod sursa (job #1498294) | Cod sursa (job #3030222) | Cod sursa (job #342724)
Cod sursa(job #342724)
//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;
long T[2100000];
char s1[2100000],s2[2100000];
int matches[1024];
long cntmatch;
int M,N;
inline int min(int a,int b) {
if (a > b) return b;
return a;
}
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);
for (int i=0;i<min(1000,cntmatch);++i) printf("%ld ",matches[i]);
fclose(stdin);
fclose(stdout);
return 0;
}