Cod sursa(job #1495265)

Utilizator cristina_borzaCristina Borza cristina_borza Data 2 octombrie 2015 20:33:18
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>

#define NMAX 2000005

using namespace std;

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

int n , m , pi[NMAX] , dp[NMAX] , nr;
char s[NMAX] , c[NMAX];

int main()
{
    f >> c + 1 >> s + 1;

    n = strlen(s + 1);
    m = strlen(c + 1);

    pi[1] = 0;
    for(int i = 2 ; i <= m ; ++i) {
        int k = pi[i - 1];
        while(k > 0 && c[i] != c[k + 1]) {
            k = pi[k];
        }

        if(c[i] == c[k + 1]) {
            pi[i] = k + 1;
        }
        else{
            pi[i] = 0;
        }
    }

    int k = 0;
    for(int i = 1 ; i <= n ; ++i) {
        while(k > 0 && s[i] != c[k + 1]) {
            k = pi[k];
        }

        if(s[i] == c[k + 1]) {
            ++k;
        }
        dp[i] = k;
    }

    for(int i = 0 ; i < n ; ++i) {
        if(dp[i] == m) {
            ++nr;
        }
    }

    g << nr << '\n';
    nr = 0;

    for(int i = 0 ; i < n ; ++i) {
        if(dp[i] == m) {
            ++nr;
            g << i - m << " ";
        }
        if(nr >= 1000){
            return 0;
        }
    }
    return 0;
}