Cod sursa(job #2063220)

Utilizator dago28Stoican Dragos dago28 Data 11 noiembrie 2017 10:15:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;


char a[2000000],s[2000000];
int p[2000000],n,af,sol[2000000];


void Citire()
{
    cin.getline(s,1000);
    cin.getline(a,1000);
}


void KMP()
{
    int i=0,j=0;
    while (j<strlen(s))
    {
        while (a[i]==s[j])
        {
            i++;
            j++;
            if (i==n)
            {
                sol[af]=j-n;
                af++;
                if (af==1000)
                    return;
                i=0;
                j=j-n+1;
            }
        }
        i=p[i-1];
        if (a[i]!=s[j])
            j++;
    }
}


void Prefix()
{
    int i=0;
    for (int j=1; j<n; j++)
    {
        if (a[i]==a[j])
        {
            p[j]=1+p[j-1];
            i++;
        }
        else
        {
            i=p[j-1];
            if (a[j]==a[i])
            {
                p[j]=1;
                i++;
            }
        }
    }

}


int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    Citire();
    n=strlen(a);
    Prefix();
    KMP();
    cout<<af<<endl;
    for (int i=0;i<af;i++)
        cout<<sol[i]<<" ";
    /*for (int i=0; i<n; i++)
        cout<<p[i]<<" ";*/
    return 0;
}