Cod sursa(job #2458347)

Utilizator severutBogdan Sever-Cristian severut Data 20 septembrie 2019 11:41:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define pb push_back
#define Nmax 2000005
using namespace std;

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

char P[Nmax],T[Nmax];
int lng,dp[Nmax];
vector<int> v;


int main()
{
    in>>P+1;
    in>>T+1;
    int n,m;
    n=strlen(P+1);
    m=strlen(T+1);
    for(int i=2;i<=n;++i)
    {
        while(lng>0 && P[lng+1]!=P[i])lng=dp[lng];
        if(P[lng+1]==P[i])++lng;
        dp[i]=lng;
    }
    lng=0;
    for(int i=1;i<=m;++i)
    {
        while(lng>0 && P[lng+1]!=T[i])lng=dp[lng];
        if(P[lng+1]==T[i])++lng;
        if(lng==n)
        {
            v.pb(i-n);
            lng=dp[lng];
        }
    }
    out<<v.size()<<'\n';
    for(int i=0;i<v.size() && i<1000;++i)out<<v[i]<<" ";
    return 0;
}