Cod sursa(job #2574774)

Utilizator mirceatlxhaha haha mirceatlx Data 6 martie 2020 09:48:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MaxLG 2000005
using namespace std;

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

int Next[MaxLG], N, M;
char str1[MaxLG], str2[MaxLG];
vector <int> Answer;

void next()
{
    int k = -1, x;
    for(x = 1; x < M; x++){
        while(k > 0 && str2[k + 1] != str2[x]){
            k = Next[x];
        }
        if(str2[k + 1] == str2[x]){
            ++k;
        }
        Next[x] = k;
    }
}

int main()
{
    int x = -1;
    cin.getline(str2,MaxLG);
    cin.getline(str1,MaxLG);
    N = strlen(str1);
    M = strlen(str2);
    next();
    for(int i = 0; i < N; i++){
        while(x > 0 && str2[x + 1] != str1[i]){
            x = Next[x];
        }
        if(str2[x + 1] == str1[i]){
            x++;
        }
        if(x == M - 1){
            Answer.push_back(i - M + 1);
        }
    }
    cout << Answer.size() << "\n";
    for(int i = 0; i < Answer.size(); i++){
        cout << Answer[i] << " ";
    }
    return 0;
}