Cod sursa(job #1639095)

Utilizator zertixMaradin Octavian zertix Data 8 martie 2016 10:55:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define longn 2000005
using namespace std;

char s1[longn],s2[longn];
int pref[longn],is2[longn],n,m,ras[1005],sol;

void prefix()
{
    int i=0,j=1;
    while (j<n)
    {
        if (s1[i]==s1[j])
            {
                pref[j]=i+1;///retin poziti, nu lungimi
                ++i;++j;
            }
        else
            if (i==0)
                ++j;
            else
                i=pref[i-1];
    }
}
void kmp()
{
    int i=0,j=0;
    while (j<m)
    {
        if (s1[i]==s2[j])
        {
            ++i;
            ++j;
            if (i==n)
            {
                sol++;
                if (sol<1001)
                    ras[sol]=j-n;
            }
        }
        else
            {
                if (i==0)
                    ++j;
                else
                    i=pref[i-1];
            }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(s1,longn,stdin);
    scanf("\n");
    fgets(s2,longn,stdin);
    n=strlen(s1);
    m=strlen(s2);
    if (s1[n-1]=='\n')
        --n;
    if (s2[m-1]=='\n')
        --m;


    prefix();
    kmp();
    printf("%d\n",sol);
    sol=min(1000,sol);
    for (int i=1;i<=sol;++i)
        printf("%d ",ras[i]);
    return 0;
}