Cod sursa(job #1382474)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 9 martie 2015 08:47:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int maxn = 2000005;

string a, b, whole;
int z[maxn], n, m;

inline int extend(string a, int i, int j) {
    int sum;
    for(sum = 0 ; j + sum < a.size() ; ++ sum)
        if(a[i + sum] != a[j + sum])
            return sum;
    return sum;
}

inline void buildz(string a) {
    int l = -1, r = -1;
    for(int i = 1 ; i < a.size() ; ++ i) {
        if(i >= r) {
            z[i] = extend(a, 0, i);
            l = i;
            r = i + z[i] - 1;
        }
        else {
            int lasti = i - l;
            if(z[lasti] <= r - l + 1)
                z[i] = z[lasti];
            else {
                z[i] = z[lasti] + extend(a, lasti + z[lasti] - 1, i + z[lasti] - 1);
                if(r < i + z[i] - 1) {
                    l = i;
                    r = i + z[i] - 1;
                }
            }
        }
    }
}

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    getline(fin, a);
    getline(fin, b);
    int aux = a.size();
    a += b;
    buildz(a);
    int ans = 0;
    vector <int> matches;
    for(int i = aux ; i < a.size() ; ++ i)
        if(z[i] >= aux) {
            ++ ans;
            if(ans <= 1000)
                matches.push_back(i - aux);
        }
    fout << ans << '\n';
    for(auto it : matches)
        fout << it << ' ';
}