Cod sursa(job #2515589)

Utilizator biopreaOprea Bianca bioprea Data 28 decembrie 2019 21:54:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.08 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()

{   int len;
    fgets(patt, 2000005, fin);
    fgets(txt, 2000005, fin);
    p = strlen(patt) - 1;
    t = strlen(txt) - 1;
     len = 0;
    lps[0] = 0; // lps[0] is always 0
    // the loop calculates lps[i] for i = 1 to M-1
     i = 1;
    while (i < p) {
        if (patt[i] == patt[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];

                // Also, note that we do not increment
                // i here
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }
    }

  /*  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; // index for txt[]
     j = 0; // index for pat[]
    while (i < t and nrap<1000) {
        if (patt[j] == txt[i]) {
            j++;
            i++;
        }

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

        // mismatch after j matches
        else if (i < t && patt[j] != txt[i]) {
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }


 /*   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;

}