Pagini recente » Cod sursa (job #2060636) | Cod sursa (job #1824948) | Cod sursa (job #1507033) | Cod sursa (job #2928445) | Cod sursa (job #552376)
Cod sursa(job #552376)
#include <cstdio>
#include <string.h>
using namespace std;
char s[2000020];
char t[2000020];
int v[2000020];
int b[2000020];
int n;
int m;
void citire()
{
gets(s);
gets(t);
n=strlen(s);
m=strlen(t);
}
void kmpp()
{
int i=0;
int j=-1;
b[i]=j;
while(i<n)
{
while(j>=0&&s[i]!=s[j])
j=b[j];
i++;
j++;
b[i]=j;
}
}
int k;
int nr=0;
void kmps()
{
int i=0;
int j=0;
while(i<m)
{
while(j>=0&&t[i]!=s[j])
j=b[j];
i++;
j++;
if(j==n)
{
v[k++]=i-j;
nr++;
j=b[j];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
kmpp();
kmps();
printf("%d\n",nr);
for(int i=0;i<k;i++)
printf("%d ",v[i]);
return 0;
}