Cod sursa(job #2222161)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 16 iulie 2018 16:22:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 2000003;

char x[NMax];
char y[NMax];
int pi[NMax];
int n;
vector<int> v;

void make_pi(char *x){
    pi[0] = -1;
    int k = -1;
    int l = strlen(x);
    for(int i = 1; i < l; ++i){
        while(k > -1 && x[k + 1] != x[i])
            k = pi[k];
        if(x[k + 1] == x[i])
            k++;
        pi[i] = k;
    }
}
void solve(char *x, char *y){
    int len_x = strlen(x);
    int len_y = strlen(y);
    int k = -1;
    for(int i = 0; i < len_y; ++i){
        while(k > -1 && x[k + 1] != y[i])
            k = pi[k];
        if(x[k + 1] == y[i])
            k++;
        if(k == len_x - 1){
            n++;
            if(n <= 1000){
                v.push_back(i - len_x + 1);
            }
        }
    }
    g << n << '\n';
    for(int i = 0; i < v.size(); ++i){
        g << v[i] << ' ';
    }
}
int main()
{
    f.getline(x,NMax);
    f.getline(y,NMax);
    make_pi(x);
    solve(x,y);
    return 0;
}