Cod sursa(job #1940849)

Utilizator bmanghiucManghiuc Bogdan bmanghiuc Data 26 martie 2017 20:36:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

    string N, M;
    f>>N>>M;

    N.insert(0, "!");
    M.insert(0, "!");

    unsigned int n = N.length() - 1;
    unsigned int m = M.length() - 1;

    int pi[n+1];
    pi[1] = 0;
    int k = 0;
    for(unsigned int i = 2; i <= n; i++){
        while(k > 0 && N[k+1] != N[i]){
            k = pi[k];
        }
        if(N[k+1] == N[i]){
            k++;
        }
        pi[i] = k;
    }

//    for(int i=1; i<= n; i++){
//        g<<pi[i]<<" ";
//    }

    int q = 0;
    int nr = 0;
    vector<int> positions;
    for(int i = 1; i <= m && nr < 1000; i++){
        while(q > 0 && N[q+1] != M[i]){
            q = pi[q];
        }
        if(N[q+1] == M[i]){
            q++;
        }
        if(q == n){
            nr++;
            positions.push_back(i);
            q = pi[q];
        }
    }

 //   g<<"n = "<<n<<'\n';
    g<<nr<<'\n';
    for(unsigned int i=0; i<nr; i++){
        g<< (positions[i] - n) <<" ";
    }



    f.close();
    g.close();

    return 0;
}