Cod sursa(job #2780175)

Utilizator alien14Razvan alien14 Data 6 octombrie 2021 11:19:06
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 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];
char T[nMax], P[mMax];
int n,m;

void Next(char *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.getline(P,255);
    fin.getline(T,1000);
    n=strlen(T);
    m=strlen(P);
    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;
}