Cod sursa(job #2932087)

Utilizator divadddDavid Curca divaddd Data 1 noiembrie 2022 21:21:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#define MAX 2000005
using namespace std;
char a[MAX],b[MAX];
int p[MAX],n,m,cnt;
vector<int> sol;

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

int main()
{
    fin >> a+1; n = strlen(a+1);
    fin >> b+1; m = strlen(b+1);
    int l = 0;
    for(int i = 2; i <= n; i++){
        while(l != 0 && a[i] != a[l+1]){
            l = p[l];
        }
        if(a[i] == a[l+1]){
            l++;
        }
        p[i] = l;
    }
    l = 0;
    for(int i = 1; i <= m; i++){
        while(l != 0 && b[i] != a[l+1]){
            l = p[l];
        }
        if(b[i] == a[l+1]){
            l++;
        }
        if(l == n){
            cnt++;
            if(sol.size() < 1000){
                sol.push_back(i-n);
            }
            l = p[l];
        }
    }
    fout << cnt << "\n";
    for(auto it: sol){
        fout << it << " ";
    }
    return 0;
}