Cod sursa(job #3243805)

Utilizator Gergo123Schradi Gergo Gergo123 Data 21 septembrie 2024 13:46:26
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream input("strmatch.in");
ofstream output("strmatch.out");

int main()
{
    string a, b;
    input>>a>>b;
    vector<int>T(a.size() + 1, 0);
    int k=0;
    for(int i=1;i<a.size();i++){
        while(k>0&&a[k]!=a[i]){
            k=T[k];
        }
        if(a[k]==a[i]){
            k++;
        }
        T[i]=k;
    }
    k=0;
    int nr=0;
    vector<int>pos;
    for(int i=0;i<b.size();i++){
        while(k>0&&a[k]!=b[i]){
            k=T[k];
        }
        if(a[k]==b[i]){
            k++;
        }
        if(k==a.size()){
            if(nr<1000) {
                pos.push_back(i-a.size()+1);
            }
            nr++;
            k=T[k-1];
        }
    }
    output<<nr<<endl;
    int limit=min(nr,1000);
    for(int i=0;i<limit;i++){
        output<<pos[i]<<" ";
    }
    return 0;
}