Pagini recente » Cod sursa (job #245006) | Cod sursa (job #1196843) | Cod sursa (job #1160745) | Cod sursa (job #1772417) | Cod sursa (job #2791187)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000001],s[2000001];
int pref[2000001],sir[2000001],nr,rez[1005],m,n;
void formare(){
int i=0,j=-1;pref[0]=-1;
while(i<m){
while(j>=0 && p[i]!=p[j]){
j=pref[j];
}
i++;
j++;
pref[i]=j;
}
return;
}
void kmp(){
int i=0,j=0;
while(i<n){
while(j>=0 && s[i]!=p[j])
j=pref[j];
i++;
j++;
if(j==m){
j=pref[j];
nr++;
if(nr<=1000){
rez[nr]=i-m;
}
}
}
}
int main()
{
f.getline(p,2000001);
f.getline(s,2000001);
m=strlen(p);n=strlen(s);
formare();
kmp();
g<<nr<<"\n";
for(int i=1;i<=(nr<=1000?nr:1000);i++)
g<<rez[i]<<" ";
}