Cod sursa(job #2515526)

Utilizator marinaoprOprea Marina marinaopr Data 28 decembrie 2019 19:44:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 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, 2000005, fin);
    fgets(txt, 2000005, fin);

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

    for(i=1; i<=p-1; ++i)
        if(patt[i] == patt[lps[i-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] = j+1;
            else
                if(patt[i] == patt[j])
                    lps[i] = 1;
                else
                    lps[i] = 0;
        }

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

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

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

            if(k>0)
                j = k;
            else
                if(k==0 and patt[0]==txt[i])
                    j = 0;
                else
                {
                    ++i;
                    j = 0;
                }
        }
    }

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

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