Pagini recente » Cod sursa (job #1476390) | Cod sursa (job #2806432) | Cod sursa (job #699637) | Cod sursa (job #2220105) | Cod sursa (job #2724241)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern,text;
int n,m;
int ans[2000001];
int lps[2000001];
void compute_lps_array(){
int len = 0;
lps[len] = 0;
int i = 1;
while(i <= n){
if(pattern[i] == pattern[len]){
++len;
lps[i] = len;
++i;
}
else{
if(len != 0){
len = lps[len-1];
}
else{
lps[i] = 0;
++i;
}
}
}
}
void kmp(){
int nr = 0;
int i = 0 , j = 0;
compute_lps_array();
while (i < m){
if(pattern[j] == text[i]){
++i;
++j;
}
if(j==n){
++nr;
ans[nr] = i-j;
j = lps[j-1];
}
else if(i < m && pattern[j] != text[i]){
if(j != 0){
j = lps[j-1];
}
else{
++i;
}
}
}
g<<nr<<endl;
for(int k=1;k<=min(nr,1000);++k){
g<<ans[k]<<" ";
}
}
int main()
{
f>>pattern>>text;
n = pattern.length();
m = text.length();
kmp();
return 0;
}