Pagini recente » Cod sursa (job #1580316) | Cod sursa (job #927266) | Cod sursa (job #2119777) | Cod sursa (job #809463) | Cod sursa (job #184187)
Cod sursa(job #184187)
#include<stdio.h>
#include<string.h>
#define MAXN 2000005
int m,i,n,nrsol;
int p[MAXN],sol[1001];
char s1[MAXN],s2[MAXN];
void prefix()
{
int k=0,i;
for(i=2;i<=m;i++)
{
while(k>0&&s2[k+1]!=s2[i])
k=p[k];
if(s2[k+1]==s2[i])
k++;
p[i]=k;
}
}
void kmp()
{
int i,k=0;
for(i=1;i<=n;i++)
{
while(k>0&&s2[k+1]!=s1[i])
k=p[k];
if(s2[k+1]==s1[i])
k++;
if(k==m)
{
nrsol++;
if(nrsol<=100)
sol[nrsol]=i-m;
k=p[m];
}
}
}
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s2, sizeof(s2), stdin);
fgets(s1, sizeof(s1), stdin);
for (; (s1[n] >= 'A' && s1[n] <= 'Z') || (s1[n] >= 'a' && s1[n] <= 'z')
|| (s1[n] >= '0' && s1[n] <= '9'); ++n);
for (; (s2[m] >= 'A' && s2[m] <= 'Z') || (s2[m] >= 'a' && s2[m] <= 'z')
|| (s2[m] >= '0' && s2[m] <= '9'); ++m);
for (i = m; i; --i) s2[i] = s2[i-1]; s2[0] = ' ';
for (i = n; i; --i) s1[i] = s1[i-1]; s1[0] = ' ';
prefix();kmp();
printf("%d\n",nrsol);
for(i=1;i<=nrsol&&i<=1000;i++)
printf("%d ",sol[i]);
return 0;
}