Cod sursa(job #2349662)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 20 februarie 2019 17:08:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

const int NMax = 4000003;

int zf[NMax];
vector<int> ans;

int main(){
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    string x,y;
    cin >> x;
    cin >> y;
    int n = x.size();
    x = x + "$" + y;
    int L = 0, R = 0;
    for(int i = 1; i < x.size(); ++i){
        if(i > R){
            L = R = i;
            while(R < x.size() && x[R - i] == x[R]){
                R++;
            }
            R--;
            zf[i] = R - i + 1;
        }else{
            if(zf[i - L] < R - i + 1){
                zf[i] = zf[i - L];
            }else{
                L = i;
                while(R < x.size() && x[R - i] == x[R]){
                    R++;
                }
                R--;
                zf[i] = R - i + 1;
            }
        }
    }
    int nr = 0;
    for(int i = n; i < x.size(); ++i){
        if(zf[i] == n){
            nr++;
            if(nr <= 1000){
                ans.push_back(i - n - 1);
            }
        }
    }
    cout << nr << '\n';
    for(auto i : ans){
        cout << i << ' ';
    }
    return 0;
}