Cod sursa(job #2239977)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 12 septembrie 2018 09:13:22
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000002]={};
vector<int> rez;
int main()
{
    string n,m;
    fin>>n>>m;
    int k=0;
    for(int i=0;i<m.length();i++)
    {
        while(k>0&&n[k]!=m[i])
            k=pi[k];
        if(n[k]==m[i])
            k++;
        pi[i+1]=k;
        if(k==n.length())
            rez.push_back(i-n.length()+1);

    }
    fout<<rez.size()<<"\n";

    for(auto x:rez)
        fout<<x<<" ";


    return 0;
}