Cod sursa(job #1830929)

Utilizator luca_robertaLuca Roberta luca_roberta Data 17 decembrie 2016 11:38:15
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 2000010

using namespace std;

char a[MAX],s[MAX];
int poz[MAX],nr,sol[MAX];

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

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

    int i=1,j=0;
    int n=strlen(a);
    while (i<n)
    {
        if (a[i]==a[j])
        {
            poz[i]=j+1;
            j++;
        }
        else
        if(j==0)
            i++;
        else
            if (i==1)
                poz[i]=0;
            else
            {
                while (a[i]!=a[j])
                {
                    j--;
                    if (j==0)
                        break;
                }
                poz[i]=poz[j];
            }
        i++;
    }
    i=0;
    j=0;
    int m=strlen(s);
    while (i<m)
    {
        if (a[j]==s[i])
        {
            i++;
            j++;
        }
        else
            if(j!=0)
            {
                j=poz[j-1];
            }
            else
                i++;
        if(j==n)
            sol[nr++]=i-n;
    }
    cout<<nr<<endl;
    for(i=0;i<nr;i++)
        cout<<sol[i]<<" ";
    return 0;
}