Cod sursa(job #2780177)

Utilizator alien14Razvan alien14 Data 6 octombrie 2021 11:22:04
Problema Potrivirea sirurilor Scor 2
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include<cstring>
#include <list>
#include <stack>
#include<bits/stdc++.h>
#define nMax 1000
#define mMax 255
using namespace std;
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int Urm[mMax];
string T,P;
int n,m;

void Next(string P)
{
    int k =-1,x;
    Urm[0] = 0;
    for(x=1;x<m;x++)
    {
        while(k>0 && P[k+1]!=P[x])
            k = Urm[k];
        if(P[k+1] == P[x])
            k++;
        Urm[k] = k;
    }
}
 
int main()
{
    int i,x=-1;
    fin>>P;
    fin>>T;
    n=T.size();
    m=P.size();
    vector<int>res;
    Next(P);
    for(i=0;i<n;i++)
    {
        while(x>0 && P[x+1]!=T[i])
            x = Urm[x];
        if(P[x+1] == T[i])
            x++;
        if(x == m-1)
        {
            res.push_back(i-m+1);
            x = Urm[x];
        }
    }

    fout<<res.size()<<'\n';
    for(i=0;i<res.size();i++)
    {
        fout<<res[i]<<" ";
    }
    return 0;
}