Cod sursa(job #1383624)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 10 martie 2015 14:50:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int maxn = 2000005;

int n, m, z[maxn * 2];
string a, b, text;

inline int expand(int i, int j) {
    int cnt = 0;
    for(cnt = 0 ; j + cnt < text.size() ; ++ cnt)
        if(text[i + cnt] != text[j + cnt])
            return cnt;
    return cnt;
}

inline void zalg() {
    int l = -1, r = -1;
    for(int i = 1 ; i < text.size() ; ++ i) {
        if(i > r) {
            z[i] = expand(0, i);
            if(z[i]) {
                l = i - z[i] + 1;
                r = i;
            }
        }
        else {
            int lasti = r - i;
            if(z[lasti] < r - i + 1)
                z[i] = z[lasti];
            else {
                z[i] = r - i + 1 + expand(r - l + 1, r + 1);
                if(i + z[i] > r) {
                    r = i + z[i];
                    l = i;
                }
            }
        }
    }
    vector <int> matches;
    for(auto i = a.size() ; i < text.size() ; ++ i)
        if(z[i] >= a.size())
            matches.push_back(i - a.size());
    fout << matches.size() << '\n';
    for(auto it : matches)
        fout << it << ' ';
}

int main() {
    getline(fin, a);
    getline(fin, b);
    text = a + b;
    zalg();
}