Pagini recente » Cod sursa (job #576369) | Cod sursa (job #209267) | Cod sursa (job #2652179) | Cod sursa (job #3197081) | Cod sursa (job #2387516)
#include <bits/stdc++.h>
#define N 2000005
int m,n;
char A[N],B[N];
int pi[N],pos[1024];
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
void KMP()
{
int q=0;
pi[1]=0;
for(int i=2;i<=m;++i)
{
while(q&&A[q+1]!=A[i]) q=pi[q];
if(A[q+1]==A[i]) ++q;
pi[i]=q;
}
}
int main()
{
int q=0,p=0;
fin.getline(A,N);
fin.getline(B,N);
while((A[m]>='A' && A[m]<='Z') || (A[m]>='a' && A[m]<='z') || (A[m]>='0' && A[m]<='9')) ++m;
while((B[n]>='A' && B[n]<='Z') || (B[n]>='a' && B[n]<='z') || (B[n]>='0' && B[n]<='9')) ++n;
for (int i=m;i;--i) A[i]=A[i-1]; A[0] = ' ';
for (int i = n; i; --i) B[i] = B[i-1]; B[0] = ' ';
KMP();
for (int i=1;i<=n;++i)
{
while(q&&A[q+1]!=B[i]) q=pi[q];
if (A[q+1]==B[i]) ++q;
if(q==m)
{
q=pi[m];
++p;
if (p<=1000)
pos[p]=i-m;
}
}
fout<<p<<'\n';
for (int i=1;i<=std::min(p,1000);++i)
fout<<pos[i]<<' ';
return 0;
}