Pagini recente » Cod sursa (job #2471571) | Cod sursa (job #2730631) | Cod sursa (job #2530364) | Istoria paginii runda/croitorasul_cel_viteaz/clasament | Cod sursa (job #1974955)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
int n,m,p[100],sol[100],nr;
void prefix(char s[],int n){
p[0]=0;
int k=0;
for(int i=1;i<n;i++){
while(k>0 && s[i]!=s[k])
k=p[k];
if(s[i]==s[k])
k++;
p[i]=k;
}
}
void kmp(char a[],int n,char b[],int m){
prefix(a,n);
int k=0;
for(int i=0;i<m;i++){
while(k>0 && a[k]!=b[i])
k=p[k];
if(a[k]==b[i])k++;
if(k==n){
k=p[n-1];
nr++;
if(nr<=1000)
sol[nr]=i-n+1;
}
}
}
int main(){
f.getline(a,2000001);
f.getline(b,2000001);
kmp(a,strlen(a),b,strlen(b));
g<<nr<<'\n';
if(nr>1000)nr=1000;
for(int i=1;i<=nr;i++)
g<<sol[i]<<' ';
}