Cod sursa(job #2515540)

Utilizator marinaoprOprea Marina marinaopr Data 28 decembrie 2019 20:12:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>
#include <string.h>

using namespace std;

FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");

int p,t,i,j,lps[2000005],nrap,ap[1001],k;
char patt[2000005],txt[2000005];

int main()
{
    fgets(patt+1, 2000005, fin);
    fgets(txt+1, 2000005, fin);
    patt[0] = txt[0] = '.';

    p = strlen(patt) - 2;
    t = strlen(txt) - 2;

    for(i=2; i<=p; ++i)
        if(patt[i] == patt[lps[i-1]+1])
            lps[i] = lps[i-1]+1;
        else
        {
            j = lps[i-1];
            while(j>0 and patt[i] != patt[j])
                j = lps[j-1];

            if(j == 0)
                lps[i] = 0;
            else
                lps[i] = j;
        }

    i = 1; j = 1;
    lps[0] = -1;
    while(i<=t and nrap<1000)
    {
        while(i<=t and j<=p and patt[j] == txt[i])
            { ++i; ++j;}

        if(j > p)
        {
            ap[++nrap] = i-p-1;
            j = lps[p]+1;
            continue;
        }
        if(i>t)
            break;

            k = lps[j-1]+1;
            while(k>0 and patt[k]!=txt[i])
                k = lps[k-1]+1;

            if(k>0)
                j = k;
            else
            {
                j = 1;
                ++i;
            }
    }

    fprintf(fout, "%d\n", nrap);
    for(i=1; i<=nrap; ++i)
        fprintf(fout, "%d ", ap[i]);

    fclose(fin);
    fclose(fout);
    return 0;
}