Pagini recente » Cod sursa (job #554622) | Cod sursa (job #2412690) | Cod sursa (job #2890521) | Cod sursa (job #3276272) | Cod sursa (job #806379)
Cod sursa(job #806379)
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
char A[2000010],B[2000010];
int pi[2000010],LA,LB,nr;
vector<int> sol;
void prefix()
{
int q=0;
pi[1]=0;
for(int i=2;i<=LA;i++)
{
while(q>0&&A[q+1]!=A[i]) q=pi[q];
if(A[q+1]==A[i]) q++;
pi[i]=q;
}
}
void potrivire()
{
int q=0;
for(int i=1;i<=LB;i++)
{
while(q>0&&A[q+1]!=B[i]) q=pi[q];
if(A[q+1]==B[i]) q++;
if(q==LA)
{
nr++;
if(nr<=1000) sol.push_back(i-q);
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A+1,B+1);
LA=strlen(A+1);
LB=strlen(B+1);
prefix();
potrivire();
printf("%d\n",nr);
for(vector<int>::iterator it=sol.begin();it!=sol.end();it++) printf("%d ",*it);
return 0;
}