Pagini recente » Cod sursa (job #88109) | Cod sursa (job #888349) | Cod sursa (job #2110422) | Cod sursa (job #2925646) | Cod sursa (job #604788)
Cod sursa(job #604788)
#include<fstream>
#include<string>
#define MAX_N 2000010
using namespace std;
char A[MAX_N],B[MAX_N];
int pi[MAX_N],sol[1005],n,m,total;
void buildPrefix()
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= m; ++i)
{
while (q && A[q+1] != A[i])
q = pi[q];
if (A[q+1] == A[i])
++q;
pi[i] = q;
}
}
void solve()
{
int q = 0;
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];
if(total < 1000)
sol[total] = i-m;
total++;
}
}
}
void show()
{
printf("%d\n",total);
for(int i = 0; i < (total < 1000 ? total : 1000); i++)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",A+1,B+1);
m = strlen(A+1);
n = strlen(B+1);
if(m > n)
{ printf("0\n"); return 0; }
buildPrefix();
solve();
show();
fclose(stdin); fclose(stdout);
return 0;
}
/*#include<fstream>
using namespace std;
int urm[255];
char t[256],p[256];
int n,m;
void urmator(char *p)
{
int k=-1,x;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0&&p[k+1]!=p[x])
k=urm[k];
if(p[k+1]==p[x])
k++;
urm[x]=k;
}
}
int main()
{
ifstream f("KMP.in");
ofstream g("KMP.out");
int x=-1,i;
f.getline(t,256);
f.getline(p,256);
n=strlen(t);
m=strlen(p);
urmator(p);
for(i=0;i<n;i++)
{
while(x>0&&p[x+1]!=t[i])
x=urm[x];
if(p[x+1]==t[i])
x++;
if(x==m-1)
g<<i-m+1<<"\n",x=urm[x];
}
return 0;
}*/