Cod sursa(job #2717350)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 7 martie 2021 11:38:29
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin("kmp.in");
ofstream fout("kmp.out");

const int LMax = 2 * 1e6;

vector <int> ans;

int n, m;
int table[LMax + 5];
char word[LMax + 5], str[LMax + 5];

void Read(){
    fin >> word >> str;
    n = strlen(word), m = strlen(str);
}

void CreateTable(){
    table[0] = -1;
    int i = 1, ind = 0;
    while (i < n){
        if (word[i] == word[ind])
            table[i] = table[ind];
        else{
            table[i] = ind;
            while (ind >= 0 && word[i] != word[ind])
                ind = table[ind];
        }
        i++, ind++;
    }
    table[i] = ind;
}

void KMP(){
    int i = 0, j = 0;
    while (j < m){
        if (word[i] == str[j]){
            i++, j++;
            if (i == n){
                ans.push_back(j - i);
                i = table[i];
            }
        }
        else{
            i = table[i];
            if (i < 0)
                i++, j++;
        }
    }
}

void Print(){
    fout << ans.size() << '\n';
    for (auto pos : ans)
        fout << pos << ' ';
    fout << '\n';
}

int main(){
    Read();
    CreateTable();
    KMP();
    Print();
    return 0;
}