Pagini recente » Cod sursa (job #3189438) | Cod sursa (job #2833996) | Cod sursa (job #45568) | Cod sursa (job #878199) | Cod sursa (job #1116137)
#include<cstdio>
#include<cstring>
#include<deque>
#define nx 2000007
using namespace std;
int v[nx],n,m,i,k;
char s[nx],t[nx];
deque<int>d;
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s+1);
n=strlen(s+1);
gets(t+1);
m=strlen(t+1);
}
void prefix()
{
for(i=2;i<=n;i++)
{
while(k && s[i]!=s[k+1])k=v[k];
if(s[k+1]==s[i])k++;
v[i]=k;
}
}
void kmp()
{
k=0;
for(i=1;i<=m;i++)
{
while(k && s[k+1]!=t[i])k=v[k];
if(s[k+1]==t[i])k++;
if(k==n)d.push_back(i-n),k=v[k];
}
}
void afisare()
{
printf("%d\n",d.size());
while(!d.empty())printf("%d ",d.front()),d.pop_front();
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}