Pagini recente » Cod sursa (job #1795084) | Cod sursa (job #1670599) | Cod sursa (job #1557716) | Cod sursa (job #441930) | Cod sursa (job #1800219)
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char s1[2000005],s2[2000005]; //s1=sirul in care cautam
//s2=sirul pe care il cautam
int j,pi[2000005],n,k,i,nr,m,poz[1005];
void prefix()
{
pi[0]=0; k=0;
for(i=1;i<=m;i++)
{
while(k>0 && s2[i]!=s2[k]) k=pi[k-1];
if(s2[k]==s2[i]) k++;
pi[i]=k;
}
} //formam vectorul de prefixe care sunt si sufixe
int main()
{
in>>s2>>s1;
m=strlen(s2)-1; //lungimea sirului model
n=strlen(s1)-1; //lungimea sirului sursa
if(m==0){
for(i=0;i<=n;i++) if(s1[i]==s2[0]){ if(nr<=1000)poz[++nr]=i-m; else nr++;}
}
else{
prefix();
//for(i=0;i<=m;i++) out<<pi[i]<<" ";
k=0;
for(i=0;i<=n-m+2;i++)
{
while(k>0&& s2[k]!=s1[i]) k=pi[k-1];
if(s2[k]==s1[i]) k++;
if(k==m+1){ if(nr<1000)poz[++nr]=i-m; else nr++;k=pi[k-1];}
}}
out<<nr<<"\n";
for(i=1;i<=nr && i<=1000;i++)
out<<poz[i]<<" ";
return 0;
}