Cod sursa(job #1830895)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 17 decembrie 2016 11:20:19
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <cstring>
#define NMAX 20000002

using namespace std;

int poz[NMAX], nr, sol[NMAX];
char c[NMAX], s[NMAX];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s", c);
    scanf("%s\n", s);

    int i=1, j=0, n=strlen(c), m=strlen(s);
    while(i<n)
    {
       if(c[i]==c[j])
           poz[i]=++j;
       else
            if(i==1)
                poz[i]=0;
       else
       {
            while(c[i]!=c[j])
            {
                j--;
                if(j==0)
                    break;
            }
            poz[i]=poz[j];
       }
       i++;
    }

    i=0, j=0;
    while(i<m)
    {
        if(c[j]==s[i])
        {
            i++, j++;

        }
        else
            if(j>0)
                j=poz[j-1];
            else
                i++;
        if(j==n)
            sol[nr++]=i-n;
    }
    printf("%d\n", nr);
    for(i=0;i<nr;i++)
        printf("%d ", sol[i]);
    return 0;
}