Pagini recente » Cod sursa (job #2027438) | Cod sursa (job #2258352) | Cod sursa (job #104770) | Cod sursa (job #1526327) | Cod sursa (job #1412079)
#include <fstream>
#include <cstring>
using namespace std;
string txt , pat;
int tab[2000005];
int sol[2000];
int ct;
void pretab(int m){
int k=-1;
tab[0]=k;
for(int i=1;i<m;i++){
while(k>-1&&pat[k]!=pat[i])k=tab[k];
k++;
tab[i]=k;
}
}
void kmp(){
int n = txt.length();
int m = pat.length();
int k;
pretab( m);
k=-1;
for(int i=0;i<n;i++){
while((k>-1)&&pat[k+1]!=txt[i])k=tab[k];
if(pat[k+1]==txt[i])k++;
if (k==m-1){
sol[ct]=i-k;
ct++;
k=tab[k];
}
}
}
int main()
{
ifstream fin("strmatch.in");
getline(fin,pat);
getline(fin,txt);
fin.close();
kmp();
ofstream fout("strmatch.out");
fout<<ct<<'\n';
for(int i=0;i<ct;i++)fout<<sol[i]<<" ";
return 0;
}