Pagini recente » Cod sursa (job #1781191) | Cod sursa (job #709782) | Cod sursa (job #2659581) | Cod sursa (job #3127249) | Cod sursa (job #2392474)
#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 BNDM(char *x, int m, char *y, int n) {
int B[N];
int i, j, s, d, last;
memset(B,0,N*sizeof(int));
s=1;
for (i=m-1; i>=0; i--){
B[x[i]] |= s;
s <<= 1;
}
j=0;
while (j <= n-m){
i=m-1; last=m;
d = ~0;
while (i>=0 && d!=0) {
d &= B[y[j+i]];
i--;
if (d != 0){
if (i >= 0)
last = i+1;
else
{v[ct++]=j;}
}
d <<= 1;
}
j += last;
}
}
*/
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;
}