Cod sursa(job #2714040)

Utilizator As932Stanciu Andreea As932 Data 1 martie 2021 10:47:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int nmx = 2e6 + 5;

int n, m, pi[nmx];
char a[nmx], b[nmx];

void read(){
    cin >> (a + 1);
    cin >> (b + 1);

    //cout << (a + 1) << " " << (b + 1) << "\n";

    n = strlen(a + 1);
    m = strlen(b + 1);
}

void prefix(){
    int k = 0;

    for(int i = 2; i <= n; i++){
        while(k > 0 && a[k + 1] != a[i])
            k = pi[k];
        if(a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
}

void kmp(){
    int q = 0;
    int ap = 0;
    vector <int> ans;

    for(int i = 1; i <= m; i++){
        while(q > 0 && a[q + 1] != b[i])
            q = pi[q];
        if(a[q + 1] == b[i])
            q++;
        if(q == n){
            ap++;
            if(ap <= 1000)
                ans.push_back(i - n);
        }
    }

    cout << ap << "\n";
    for(auto it : ans)
        cout << it << " ";
}

int main()
{
    read();
    prefix();
    kmp();

    return 0;
}