Pagini recente » Cod sursa (job #2334020) | Cod sursa (job #924848) | Cod sursa (job #1995281) | Cod sursa (job #90372) | Cod sursa (job #2187249)
#include<fstream>
#include<cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int pi[2000100],d[2000100],k,x;
char A[2000100],B[2000100];
int main()
{
f.getline(A+1, 2000100);
f.getline(B+1, 2000100);
pi[1]=0;
A[0]=B[0]=' ';
int n=strlen(A)-1;
int m=strlen(B)-1;
k=0;
for(int i=2;i<=n;++i){
while(k&&A[i]!=A[k+1]) k=pi[k];
if(A[k+1]==A[i]) ++k;
pi[i]=k;
}
k=0;
for(int i=1;i<=m;++i){
while(k&&B[i]!=A[k+1]) k=pi[k];
if(B[i]==A[k+1]) ++k;
d[i]=k;
if(d[i]==n) x++;
}
g<<x<<'\n';
int nr=0;
for(int i=1;i<=m;++i){
if(d[i]==n){
g<<i-n<<" ";
nr++;
if(nr==x||nr==1000) return 0;
}
}
return 0;
}