Cod sursa(job #1508745)

Utilizator GuzgleteBumbu Alexandru Guzglete Data 22 octombrie 2015 21:59:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

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

char p[2000010],s[2000010];
int pref[2000010],rez[1010];
int i,j,nr,n,m;

void prefix (int n)
{
    pref[0]=0;
    i=1;
    j=0;
    while (i<n)
    {
        if (p[i]==p[j])
        {
            pref[i]=j+1;
            i++;
            j++;
        }
        else
            if (j==0)
                pref[i++]=0;
        else
            j=pref[j-1];
    }
}

void rezultat (int n, int m)
{
    i=0;
    j=0;
    while (i<n)
    {
        if (s[i]==p[j])
        {
            i++;
            j++;
            if (j==m)
            {
                nr++;
                rez[nr]=i-m;
                j=pref[j-1];
            }
        }
        else
            if (j==0)
                i++;
        else
            j=pref[j-1];
    }
}

int main()
{
    fin.getline (p,2000010);
    fin.getline (s,2000010);

    n=strlen(p);
    prefix(n);
    n=strlen(s);
    m=strlen(p);
    rezultat(n,m);
    fout<<nr<<"\n";
    i=1;
    while (i<=nr && i<=1000)
    {
        fout<<rez[i]<<" ";
        i++;
    }
    return 0;
}