Cod sursa(job #2203345)

Utilizator DordeDorde Matei Dorde Data 11 mai 2018 22:52:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
ifstream f (in);
ofstream g (out);
int const NM = 2000007;
char pat [NM] , v [NM];
int lps [NM];
int n , m ;
vector <int> v2;
/// lps
void LPS()
{
    int l = 0 , i = 1;
    while(i < n)
    {
        if(pat [i] == pat [l])
        {
            ++ l;
            lps [i] = l;
            ++ i;
        }
        else
        {
            if(l )
                l = lps [l - 1];
            else
                lps [i] = 0 , ++ i;
        }
    }
}
int ans;
void kmp ()
{
    int i , j;
    i = j = 0;
    while(i < m)
    {
        if(pat [j] == v [i])
            ++ i , ++ j;
        if(j == n)
        {
            ++ ans , v2  . push_back (i - j) ;
            j = lps [j - 1];
        }
        else
            if(i < m && pat [j] != v [i])
            {
                if(j)
                    j = lps [j - 1];
                else
                    ++ i;
            }
    }
}
int main()
{
    int i , j , l ;
    f >> pat >> v ;
    n = strlen(pat);
    m = strlen(v);
    LPS();
    kmp ();
    g << ans << '\n';
    for(i = 0 ; i < min(ans , 999) ; ++ i)
        g << v2 [i] << ' ';
    return 0;
}