Pagini recente » Cod sursa (job #468422) | Cod sursa (job #1001604) | Cod sursa (job #649210) | Cod sursa (job #625022) | Cod sursa (job #2187227)
#include<fstream>
#include<cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int pi[200006],d[200006],k,x;
char A[200006],B[200006];
int main()
{
f.getline(A+1, 2000006);
f.getline(B+1, 2000006);
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;
}