Cod sursa(job #3242723)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 13 septembrie 2024 21:03:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 5;
int lps[N];
void kmp(string &s) {
    int k = 0;
    for(int i = 2; i < s.length(); i++) {
        while(k > 0 && s[i] != s[k + 1])
            k = lps[k];
        if(s[i] == s[k + 1]) {
            k++;
        }
        lps[i] = k;
    }
}
// #define HOME

int main() {
#ifndef HOME
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
#endif
    string s, t;
    cin >> s >> t;
    int m = s.length(), n = t.length();
    s = " " + s;
    t = " " + t;
    vector <int> ans;
    kmp(s);
    int k = 0;
    for(int i = 1; i <= n; i++) {
        while(k > 0 && t[i] != s[k + 1]) {
            k = lps[k];
        }
        if(t[i] == s[k + 1]) {
            k++;
        }
        if(k == m) {
            ans.push_back(i-m);
            if(ans.size() >= 1000) {
                cout << ans.size() << "\n";
                for(int x : ans) {
                    cout << x << " ";
                }
                return 0;
            }
            k = lps[m];
        }
    }
    cout << ans.size() << "\n";
    for(int x : ans) {
        cout << x << " ";
    }
    return 0;
}