Cod sursa(job #2367598)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 5 martie 2019 11:38:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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 = " " + haystack;
    needle = " " + needle;

    vector<int> kmp(needle.size(), 0);
    int k = 0;
    for(int i = 2; i < needle.size(); i ++) {
        while(k > 0 && needle[k + 1] != needle[i])
            k = kmp[k];
        if(needle[k + 1] == needle[i])
            k ++;
        kmp[i] = k;
    }

    k = 0;
    int sz = needle.size() - 1, ans = 0;
    vector<int> pos;
    for(int i = 1; i < haystack.size(); i ++) {
        while(k > 0 && haystack[i] != needle[k + 1])
            k = kmp[k];
        if(needle[k + 1] == haystack[i])
            k ++;

        if(k == sz) {
            k = kmp[k];
            if(pos.size() < 1000)
                pos.push_back(i - sz);
            ans ++;
        }
    }

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

    return 0;
}