Cod sursa(job #2207119)

Utilizator DordeDorde Matei Dorde Data 24 mai 2018 22:27:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <fstream>
using namespace std;
int const NM = 2e6 + 7;
char pat [NM] , v [NM];
int lps [NM] , n , m , best;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
vector <int> sol;
inline void Lps ()
{
    int i , j ;
    int a = 0 , b = 1;
    while(b < m)
    {
        if(pat [a] == pat [b])
        {
            ++ a;
            ++ b;
            lps [b - 1] = a;
        }
        else
        {
            if(a)
                a = lps [a - 1];
            else
                lps [b] = 0 , ++ b;
        }
    }
    return;
}
int main()
{
    FILE *cin , *cout;
    int i , j;
    cin = fopen (in , "r");
    cout = fopen (out , "w");
    fgets (pat , NM , cin);
    fgets (v , NM , cin);
    n = strlen (v) - 1;
    m = strlen (pat) - 1;
    Lps ();
    for(i = 0 , j = 0 ; j < n ; )
    {
        if(pat [i] == v [j])
        {
            ++ i;
            ++ j;
        }
        if(i == m)
        {
            ++ best;
            sol . push_back (j - i);
            i = lps [m - 1];
        }
        else
            if(j < n && pat [i] != v [j] )
                if(i)
                    i = lps [i - 1];
                else
                    ++ j;
    }
    fprintf (cout , "%d\n" , best);
    best = min (best , 1000);
    for(i = 0 ; i < best ; ++ i)
        fprintf (cout , "%d " , sol [i]);
    return 0;
}