Cod sursa(job #2232742)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 20 august 2018 20:47:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

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

const int NMax = 2000003;

string x,y;
int k;
int pi[NMax];

void KMP(string x, string y){
    int k = -1;
    pi[0] = -1;
    for(int i = 1; i < x.size(); ++i){
        while(k >= 0 && x[k + 1] != x[i])
            k = pi[k];
        if(x[k + 1] == x[i])
            k++;
        pi[i] = k;
    }
    int ans = 0;
    k = -1;
    vector<int> v;
    for(int i = 0; i < y.size(); ++i){
        while(k >= 0 && x[k + 1] != y[i])
            k = pi[k];
        if(x[k + 1] == y[i])
            k++;
        if(k == x.size() - 1){
            ans++;
            if(ans <= 1000){
                v.push_back(i - x.size() + 1);
            }
        }
    }
    g << ans << '\n';
    for(int i = 0; i < v.size(); ++i){
        g << v[i] << ' ';
    }
}
int main(){
    f >> x;
    f >> y;
    KMP(x,y);
    return 0;
}