Pagini recente » Cod sursa (job #2602299) | Cod sursa (job #2341220) | Cod sursa (job #2541177) | Cod sursa (job #311022) | Cod sursa (job #342516)
Cod sursa(job #342516)
//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 <string>
using namespace std;
int T[2000000];
int matches[2000000];
int cntmatch;
string s1,s2;
void make_table() {
T[0] = -1;
T[1] = 0;
int pos = 2,cnd = 0;
while (pos < s2.length()) {
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;
while (m + i < s1.length()) {
if (s2[i] == s1[m + i]) {
++i;
if (i == s2.length()) {
matches[cntmatch++] = m;
i = 0;
++m;
}
} else {
m = m + i - T[i];
if (i > 0) i = T[i];
}
}
return s1.length();
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin,s2);
getline(fin,s1);
make_table();
search_string();
fout << cntmatch << endl;
for (int i=0;i<min(1000,cntmatch);++i) fout << matches[i] + 1 << " ";
fout << endl;
fin.close();
fout.close();
return 0;
}