Pagini recente » Cod sursa (job #782616) | Cod sursa (job #2934245) | Cod sursa (job #1333872) | Cod sursa (job #2324868) | Cod sursa (job #344857)
Cod sursa(job #344857)
//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>
#include <ctime>
using namespace std;
long T[2100000];
char s1[2100000],s2[2100000];
long matches[1024];
long cntmatch;
int M,N;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
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;
}
bool isalphachar(char c) {
return (((c >= 'A') && (c <= 'Z')) || ((c >= 'a') && (c <= 'z')) || ((c>='0') && (c<='9')));
}
int main() {
ios::sync_with_stdio(false);
fin >> s2;
fin >> s1;
cerr << clock() << endl;
M = 0;
N = 0;
for (;isalphachar(s2[M]);++M);
for (;isalphachar(s1[N]);++N);
make_table();
search_string();
fout << cntmatch << "\n";
int k = (cntmatch > 1000) ? 1000 : cntmatch;
for (int i=0;i<k;++i) fout << matches[i] << " ";
fin.close();
fout.close();
return 0;
}