Cod sursa(job #1830917)

Utilizator gabriela.leonteLeonte Gabriela gabriela.leonte Data 17 decembrie 2016 11:34:09
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char a[1000005],c[1000005];
int b[1000005];
int aparitii[1000005];

int main()
{
    freopen("strmatch.in","r",stdin);
 //   freopen("strmatch.out","w",stdout);
    gets(a);
    gets(c);
    int n=strlen(a);
    int i=1;
    int j=0;
    b[0]=0;
    while(i<n)
    {
        if(a[i]==a[j])
        {
            b[i]=j+1;
            j++;
            i++;
        }
        else
        {
            if(j==0)
            {
                b[i]=0;
                i++;
            }
            else
            {
                while(a[i]!=a[j])
                {
                    j--;
                    j=b[j];
                    if(j==0)
                    {
                        b[i]=0;
                        i++;
                        break;
                    }
                }
            }
        }
    }
    j=0;
    int apar=0;
    int l = strlen(c);
    for(int i=0; i<l; i++)
    {
        if(c[i]==a[j])
        {
            j++;
        }
        else
        {
            if(j!=0)
            {
                j=b[j-1];
            }
        }

        if(j==n)
        {
            aparitii[apar]=i-n+1;
            apar++;
            j = b[j - 1];
        }

    }
    printf("%d\n", apar);
    if(apar>1000)
        apar=1000;
    for(int i=0;i<apar;i++)
        printf("%d ", aparitii[i]);
    return 0;
}