Cod sursa(job #2279740)

Utilizator Turturica_DorinTurturica Dorin Turturica_Dorin Data 9 noiembrie 2018 22:02:05
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <cstring>

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

#define val 2000005

char P[ val ], T[ val ];
int n, m, i, j, D[ val ], rez, inc, v[ val ];

int main()
{
    fin.get( P, val );
    fin.get();
    fin.get( T, val );
    n = strlen( P );
    m = strlen( T );
    i = 0;
    for ( j = 1; j <= n - 1; j++ )
    {
        if ( P[ j ] == P[ i ] )
        {
            D[ j ] = D[ j - 1 ] + 1;
            i++;
        }
        else
        {
            D[ j ] = 0;
            i = 0;
        }
    }

    j = 0;
    for ( i = 0; i <= m - 1; i++ )
    {
        if ( T[ i ] == P[ j ] )
        {
            if ( j == n - 1 )
            {
                rez++;
                v[ rez ] = inc;
                inc = i - D[ j ] + 1;
                j = D[ j ];
            }
            else
            {
                if ( j == 0 )
                {
                    inc = i;
                }
                j++;
            }
        }
        else
        {
            if ( j == 0 )
            {
                j = 0;
            }
            else
            {
                /// sau while ajung cu j la 0, repet conditiile de mai jos
                inc = i - D[ j - 1 ];
                j = D[ j - 1 ];
                if ( T[ i ] == P[ j ] )
                {
                    j++;
                }
                else
                {
                    j = 0;
                }
            }
        }
    }

    fout<< rez <<'\n';
    for ( i = 1; i <= rez; i++ )
    {
        fout<< v[ i ] << ' ';
    }
    return 0;
}