Cod sursa(job #1771393)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 5 octombrie 2016 16:26:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

#define NMax 2000003
using namespace std;

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

char s[2*NMax];
int kmp[2*NMax];
int S,L,ans;
vector<int> A;

int main()
{
    f.getline(s,2*NMax);
    S = strlen(s);
    L = S;
    s[S] = '#';
    f.getline(s + S + 1,2*NMax);
    S = strlen(s);

    kmp[0] = 0;

    for(int i = 1; i < S; ++i){
        int j = kmp[i - 1];
        while(j > 0 && s[i] != s[j])
            j = kmp[j - 1];
        if(s[i] == s[j])
            kmp[i] = j + 1;
        if(kmp[i] == L && ans < 1000){
            ++ans;
            if(ans < 1000)
                A.push_back(i - L - L);
        }
    }
    g << ans << '\n';
    for(int i = 0; i < A.size(); ++i){
        g << A[i] << ' ';
    }
    return 0;
}