Cod sursa(job #2367572)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 5 martie 2019 11:30:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & -x)

using namespace std;

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

int main() {

    string needle, haystack;
    in >> needle >> haystack;
    haystack = " " + needle + haystack;

    int sz = needle.size();
    vector<int> kmp(haystack.size(), 0);
    int k = 0, ans = 0;
    vector<int> pos;

    for(int i = 2; i < haystack.size(); i ++) {
        while(k > 0 && haystack[k + 1] != haystack[i])
            k = kmp[k];

        if(haystack[k + 1] == haystack[i])
            k ++;
        kmp[i] = k;

        if(kmp[i] == sz) {
            k = kmp[k];
            if(i < 2 * sz)
                continue;

            if(pos.size() < 1000)
                pos.push_back(i - 2 * sz);
            ans ++;
        }
    }

    out << ans << "\n";
    for(auto it : pos)
        out << it << " ";

    return 0;
}