Pagini recente » Cod sursa (job #2082364) | Statistici popa marilena adelina (marilena) | Cod sursa (job #1294832) | Cod sursa (job #731453) | Cod sursa (job #870714)
Cod sursa(job #870714)
#include<fstream>
#include<string>
using namespace std;
const int NM=2000005;
string T,P;
int z[NM+NM];
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N,i,j,l,L,r,p,k,M,nr=0;
getline(fin,P); getline(fin,T); M=P.length();
P=" "+P+"$"+T; L=P.length()-1;
z[1]=0; l=r=0;
for(i=2;i<=L;++i)
{
if(i>r){
k=0;
while(P[k+1]==P[i+k] && i+k<=L)++k;
z[i]=k;
if(k>0){ l=i; r=l+k-1; }
}
else
if(z[i-l+1]< (r-i+1)) z[i]=z[i-l+1];
else
{
z[i]=z[i-l+1];
k=0;
while(P[r+k+1]==P[k+z[i]+1])++k;
z[i]+=k;
if(k>0){ l=i; r=l+k-1; }
}
}
//for(i=1;i<=L;++i)fout<<z[i]<<' ';
for(i=M+1;i<=L;++i)if(z[i]==M)++nr;
fout<<min(nr,1000)<<'\n';
for(i=M+1;i<=L && nr;++i)if(z[i]==M){ --nr; fout<<i-M-2<<" "; }
return 0;
}