Cod sursa(job #1813791)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 23 noiembrie 2016 12:08:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int nmax = 2e6 + 10;

string a, str;
int z[nmax<<2];

int cnt;
vector < int > ans;

void input() {
    fin >> a >> str;
}

void run_Z(string s) {
    int L, R; L = R = 1;
    for (int i = 2; i < (int)s.size(); ++i) {
        if (i > R) {
            for (L = R = i; R < (int)s.size() && s[R] == s[R-i+1]; ++R); --R;
            z[i] = R - i + 1;
        }
        else {
            //z[i] >= min(z[i-L+1], R - i + 1)
            if (z[i-L+1] < R - i + 1)
                z[i] = z[i-L+1];
            else {
                for (L = i; R < (int)s.size() && s[R] == s[R-i+1]; ++R); --R;
                z[i] = R - i + 1;
            }
        }
    }
}

void output() {
    for (int i = (int)a.size() + 1; i <= (int)a.size() + (int)str.size(); ++i)
        if (z[i] >= (int)a.size()) {
            cnt++;
            if (cnt <= 1000) ans.push_back(i-(int)a.size()-1); //0-indexed
        }

    fout << cnt << '\n';
    for (auto &it : ans) fout << it << ' ';
}

int main()
{
    input();
    run_Z(' ' + a + str);
    output();

    return 0;
}