Cod sursa(job #1537889)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 28 noiembrie 2015 11:40:01
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
#define nmax 2000010

using namespace std;

char a[nmax],b[nmax],pi[nmax];
int n,m,st[nmax],vf;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void precalc()
{
    int i=0,j=1;
    pi[i]=0;
    while(j<n)
    {
        if(a[i]!=a[j])
        {
            if(i==0)
                pi[j++]=0;
            else
                i=pi[i-1];
        }
        else
        {
            pi[j]=i+1;
            i++;
            j++;
        }
    }
}

void rezolv()
{
    int i=0,j=0;
    while(j<m)
    {
        if(a[i]!=b[j])
        {
            if(i==0)
                j++;
            else
                i=pi[i-1];
        }
        else
        {
            i++;
            j++;
            if(i==n)
                st[++vf]=j-n;
        }
    }
}

void afisare()
{
    fout<<vf<<"\n";
    for(int i=1;i<=vf;i++)
        fout<<st[i]<<" ";
    fout<<"\n";
}

int main()
{
    fin>>a>>b;
    n=strlen(a);
    m=strlen(b);
    precalc();
    rezolv();
    afisare();
    return 0;
}