문자열 알고리즘 시간 측정 코드

#include <iostream>
#include <cstring>
#include <chrono>
#include <climits>

using namespace std;
//namespace chrono = std::chrono;

//시간 측정용 클래스입니다.
class Timer
{
public:
    void start() //타이머를 가동합니다.
    {
        start_point = chrono::system_clock::now();
    }

    void stop() //타이머를 중단합니다.
    {
        stop_point = chrono::system_clock::now();
    }

    void clear() //값을 초기화합니다.
    {
        start_point = chrono::time_point<chrono::system_clock>::min();
        stop_point = chrono::time_point<chrono::system_clock>::min();
    }

public:
    template<class seconds_t>
    long long get_time() const //측정 메서드의 템플릿입니다.
    {
        return chrono::duration_cast<seconds_t>(stop_point - start_point).count();
    }

    long long get_nano() const //나노세컨드 단위입니다.
    {
        return get_time<chrono::nanoseconds>();
    }

    long long get_micro() const //마이크로세컨드 단위입니다.
    {
        return get_time<chrono::microseconds>();
    }

    long long get_milli() const //밀리세컨드 단위입니다.
    {
        return get_time<chrono::milliseconds>();
    }

    long long get_seconds() const //세컨드 단위입니다.
    {
        return get_time<chrono::seconds>();
    }

    long long get_minutes() const //분 단위입니다.
    {
        return get_time<chrono::minutes>();
    }

    long long get_hours() const //시간 단위입니다.
    {
        return get_time<chrono::hours>();
    }

private:
    chrono::time_point<chrono::system_clock> start_point; //시작지점입니다.
    chrono::time_point<chrono::system_clock> stop_point; //중단지점입니다.

public:
    Timer() = default;
    Timer(const Timer&) = default;
    Timer(Timer&&) = default;
    Timer& operator= (const Timer&) = default;
    Timer& operator= (Timer&&) = default;
    virtual ~Timer() = default;

};

const char* mystrstr (const char * str1, const char * str2)
{
    char *cp = (char *) str1;
    char *s1, *s2;

    if ( !*str2 ) // *str2 != '\0' 
        return((char *)str1);

    while (*cp) // cp != NULL
    {
        s1 = cp;
        s2 = (char *) str2;


        while ( *s1 && *s2 && !(*s1-*s2) ) // (*s1 != '\0') && (*s2 != '\0') && (*s1 == *s2)
                s1++, s2++;

        if (!*s2) // *s2 == '\0'
                return(cp);

        cp++;
    }
    return(NULL);
}

const char* bf_match(const char* txt, const char* pat){
	int pt=0, pp=0;

	while(txt[pt] && pat[pp]){
		if(txt[pt]==pat[pp])
			pt++, pp++;
		else{
			pt=pt-pp+1;
			pp=0;
		}
	}

	if(!pat[pp])
		return txt+(pt-pp);

	return NULL;
}

const char* kmp_match(const char* txt, const char* pat){
	int pt=1, pp=0, skip[1024];

	skip[pt]=0;

	while(pat[pt]){
		if(pat[pt]==pat[pp])
			skip[++pt]=++pp;
		else if(pp==0)
			skip[++pt]=pp;
		else
			pp=skip[pp];
	}

	pt=pp=0;

	while(txt[pt] && pat[pp]){
		if(txt[pt]==pat[pp])
			pt++, pp++;
		else if(pp==0)
			pt++;
		else
			pp=skip[pp];
	}

	if(!pat[pp])
		return txt+(pt-pp);

	return NULL;

}

const char* bm_match(const char* txt, const char* pat){
	int pt, pp, txt_len=strlen(txt), pat_len=strlen(pat);

	int skip[UCHAR_MAX + 1];

	for(pt=0; pt<=UCHAR_MAX; pt++)
		skip[pt]=pat_len;

	for(pt=0; pt<pat_len-1; pt++)
		skip[pat[pt]]=pat_len-pt-1;

		

	while(pt<txt_len){
		pp=pat_len-1;
		while(txt[pt]==pat[pp]){
			if(!pp)
				return txt+pt;

			pp--;
			pt--;

		}
		pt+=(skip[txt[pt]] > pat_len-pp) ? skip[txt[pt]] : pat_len-pp;
	}

	return NULL;
}

int main() {
	// your code goes here
	const char* txt="KinggodZero";
	const char* pat="godZ";

	int len=strlen(pat);

	cout<<"원본 텍스트 : "<<txt<<'\n';

	Timer timer;
	timer.start();
	const char* rslt1=mystrstr(txt, pat);
	timer.stop();

	cout<<"mystrstr 함수\n";
	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';
	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=strstr(txt, pat);
	timer.stop();

	cout<<"\nstrstr 함수\n";
	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';

	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=bf_match(txt, pat);
	timer.stop();

	cout<<"\nbf_match 함수\n";

	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';
	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=kmp_match(txt, pat);
	timer.stop();

	cout<<"\nkmp_match 함수\n";

	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';

	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	timer.start();
	rslt1=bm_match(txt, pat);
	timer.stop();

	cout<<"\nbm_match 함수\n";

	if(rslt1){
		cout<<"찾은 패턴 : ";
		for(int i=0;i<len;i++)
			cout<<rslt1[i];
		cout<<'\n';
	}
	else
		cout<<"패턴을 찾지 못하였습니다.\n";

	cout<<"수행시간 (nano second) : "<<timer.get_nano()<<" nanoseconds\n";

	return 0;
}