Cod sursa(job #1922483)

Utilizator Victor24Vasiesiu Victor Victor24 Data 10 martie 2017 17:39:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
using namespace std;

string pat, txt;

int lpat, ltxt, dp[2000005], i, nr, sol[2000005];

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

void din ()
{
    int i=0, j = 1;

    while ( j < lpat )
    {
        if ( pat [i] == pat [j] )
        {
            dp[j] = i + 1;
            i++;
            j++;
        }
        else
        {
            if ( i != 0 )
            {
                i = dp [i-1];
            }
            else
            {
                j++;
            }
        }
    }

}

void rez()
{
    int i = 0, j = 0;

    while ( j < ltxt )
    {
        if ( pat [ i ] == txt [ j ] )
        {
            i++;
            j++;
        }
        else
        {
            if ( i != 0 )
            {
                i = dp [ i - 1 ];
            }
            else
            {
                j++;
            }
        }

        if ( i == lpat )
        {
            nr++;
            sol [ nr ] = j - lpat ;
        }

    }

}

int main ()
{
    f>>pat>>txt;

    lpat = pat.size();
    ltxt = txt.size();

    din();
    rez();

    g<<nr<<'\n';

    for ( i = 1 ; i <= nr && i <= 1000 ; i++ )
    {
        g<<sol[i]<<" ";
    }

    return 0;
}