Cod sursa(job #1399555)

Utilizator 4ONI2015oni2015 4ONI2015 Data 24 martie 2015 20:06:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
char s[2000005],t[2000005];
int p[2000005],n;
vector<int>sol;
void prefix()
{
    int k=0,i;
    n=strlen(s+1);
    for(i=2;i<=n;i++)
    {
        while(k&&s[k+1]!=s[i])k=p[k];
        if(s[i]==s[k+1])
            k++;
        p[i]=k;
    }
}
void kmp()
{
    int k=0,m=strlen(t+1),i;
    for(i=1;i<=m;i++)
    {
        while(k&&s[k+1]!=t[i])k=p[k];
        if(t[i]==s[k+1])
            k++;
        if(k==n)
            sol.pb(i-n);
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",s+1,t+1);
    prefix();
    kmp();
    printf("%d\n",sol.size());
    for(auto it:sol)
        printf("%d ",it);
    return 0;
}