Cod sursa(job #2040232)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 15 octombrie 2017 15:26:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <string>
using namespace std;
ofstream fout("strmatch.out");
ifstream fin("strmatch.in");

string s;
string s1;
int n;
int n1;
int l[2000010];
int a;
int sol[1010];

void makeSufix(){
    l[0] = 0;
    int k = -1;
    for(int i = 1; i < n; i++){
        k = l[i - 1] - 1;
        while(s[k + 1] != s[i] && k > -1)
            k = l[k] - 1;
        if(s[k + 1] == s[i]){
            k++;
        }

        l[i] = k + 1;
    }
}

void kmp(){
    int k = -1;

    for(int i = 0; i < n1; i++){
        while(s[k + 1] != s1[i] && k > -1)
            k = l[k] - 1;
        if(s[k + 1] == s1[i]){
            k++;
        }
        if(k == n - 1){
            if(a <= 1000) sol[++a] = i - n + 1;
            else a++;

            k = l[k] - 1;
        }
    }

    fout << a << '\n';

    for(int i = 1; i <= min(a,1000); i++){
        fout << sol[i] << ' ';
    }
}

int main()
{
    fin >> s;
    n = s.size();
    fin >> s1;
    n1 = s1.size();

    makeSufix();
    kmp();

    return 0;
}