Cod sursa(job #2275311)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 3 noiembrie 2018 00:49:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

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

int main() {
    string target, s;
    in >> target >> s;
    s = target + s;

    vector<int> z(s.size(), 0);
    z[0] = 1;
    int l = 0, r = 0, ans = 0;
    vector<int> sol;
    for(int i = 1; i < s.size(); i ++) {
        if(s[i] > r) {
            int j = 0;
            while(j + i < s.size() && s[j] == s[j + i])
                j ++;
            r = i + j - 1;
            l = r - j;
            z[i] = j;
        } else {
            int pretender = i - l + 1;
            z[i] = z[pretender];
            if(z[pretender] >= (r - i + 1)) {
                int j = 0;
                while(j + z[pretender] + i < s.size() && s[j + z[pretender] + 1] == s[j + i + z[pretender]])
                    j ++;
                z[i] += j;
            }
            if(i + z[i] - 1 > r) {
                r = i + z[i] - 1;
                l = i;
            }
        }
        if(z[i] >= target.size()) {
            ans ++;
            if(ans <= 100)
                sol.push_back(i - target.size());
        }
    }
    out << ans << "\n";
    for(auto it : sol)
        out << it << " ";

    return 0;
}