Cod sursa(job #2591938)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 31 martie 2020 18:19:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
const int MMAX = 2000000;
int urm[MMAX + 5];
string t , p;
vector <int> ans;
int main()
{
    freopen("strmatch.in" , "r" , stdin);
    freopen("strmatch.out" , "w" , stdout);
    int n , m , i , k , nr;
    getline(cin , p);
    getline(cin , t);
    n = t.length();
    m = p.length();
    k = -1;
    urm[0] = 0;
    for(i = 1 ; i < m ; i ++)
    {
        while(k > 0 && p[k + 1] != p[i])
            k = urm[k];
        if(p[k + 1] == p[i])
            k ++;
        urm[i] = k;
    }
    k = -1;
    nr = 0;
    for(i = 0 ; i < n ; i ++)
    {
        while(k > 0 && p[k + 1] != t[i])
            k = urm[k];
        if(p[k + 1] == t[i])
            k ++;
        if(k == m - 1)
        {
            nr ++;
            if(ans.size() < 1000)
                ans.push_back(i - m + 1);
            k = urm[k];
        }
    }
    printf("%d\n" , nr);
    for(i = 0 ; i < ans.size() ; i ++)
        printf("%d " , ans[i]);
    return 0;
}