Cod sursa(job #2902204)

Utilizator LuciBBadea Lucian LuciB Data 15 mai 2022 21:05:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

const int NMAX = 2e6;

int z[2 * NMAX + 1];

string s;

void zAlgorithm() {
    int l, r;
    l = r = 0;
    for(int i = 1; i < s.size(); i++) {
        if(i > r) {
            l = r = i;
            while(r < s.size() && s[r - l] == s[r])
                r++;
            r--;
            z[i] = r - l + 1;
        } else if(z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        } else {
            l = i;
            while(r < s.size() && s[r - l] == s[r])
                r++;
            r--;
            z[i] = r - l + 1;
        }
    }
}
string a, b;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ans[NMAX];
int main() {
    fin >> a >> b;
    s = a + '%' + b;
    zAlgorithm();
    int x = 0;
    for(int i = 1; i < s.size(); i++) {
        if(z[i] == a.size()) {
            ans[x++] = i - (int)a.size() - 1;
        }
    }
    fout << x << endl;
    for(int i = 0; i < x; i++)
        fout << ans[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}