문자열 속 패턴 찾기, DAT(Direct Address Table)

문자열 속 패턴 찾기

배열에 Pattern 존재 여부 판단은 

Flag와 함수 쓰는 법 두가지 있다.

 

함수 사용

#include <iostream>
using namespace std;
char vect[10] = "BTABCQABC", pattern[4];

int isPattern(int index)
{
    for(int i=0; i<3; i++)
    {
        if(vect[index+i] != pattern[i])
            return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> pattern;
    for(int i=0; i<7; i++)
    {
        if(isPattern(i))
            cout << "발견 :" << i << '\n';
    }
    return 0;
    
}

Flag 사용

#include <iostream>
using namespace std;
char vect[10] = "BTABCQABC";
char pattern[4];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int flag = 0;
    cin >> pattern;
    for(int i=0; i<7; i++)
    {
        flag = 0;
        for(int j=0; j<3; j++)
        {
            if(vect[i+j] != pattern[j])
            {
                flag = 1;
                break;
            }
        }
        if(flag == 0)
        {
            cout << "index : " << i << " 발견" << '\n';
        }
    }
    return 0;
}

 

2차 배열에서 패턴 찾기도 동일하게 풀 수 있다.

이 경우에도 flag와 함수 둘 다 가능하지만 결국 똑같은 동작을 하기에 함수만 구현해볼 것이다.

#include <iostream>
using namespace std;
int vect[6][3] = {
    3, 5, 1,
    2, 4, 5,
    3, 6, 1,
    3, 1, 1,
    4, 5, 6,
    2, 4, 5
}, pattern[3];

int isPattern(int row)
{
    for(int i=0; i<3; i++)
    {
        if(vect[row][i] != pattern[i])
            return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i=0; i<3; i++)
        cin >> pattern[i];
    for(int i=0; i<6; i++)
    {
        if(isPattern(i))
        {
            cout << "index : " << i << " 발견\n";
        }
    }
    return 0;
}

 

2차 배열에서 패턴을 찾을 때 패턴보다 2차 배열의 크기가 더 크다면 한칸씩 이동하면서 비교해야한다.

이 때 열이 0~4까지만 존재하기에 0부터 2까지만 검사해주어야 한다. 3부터 3칸을 검사하면 에러가 난다.

#include <iostream>
using namespace std;
int vect[6][5] = {
    3, 5, 1, 4, 1,
    2, 4, 5, 0, 0,
    3, 6, 3, 4, 1,
    3, 1, 1, 3, 2,
    4, 5, 3, 4, 1,
    2, 4, 5, 5, 6
}, pattern[3];

int isPattern(int row, int col)
{

    for(int i=0; i<3; i++)
    {
        if(vect[row][col+i] != pattern[i])
            return 0;
    }

    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i=0; i<3; i++)
        cin >> pattern[i];
    for(int i=0; i<6; i++)
    {
        for(int j=0; j<3; j++) // 2까지만 돌려야 함
        {
            if(isPattern(i, j))
            {
                cout << "index : " << i << " 발견\n";
            }
        }

    }
    return 0;
}

 

DAT

DAT는 값을 index로 활용하는 코딩 방식으로 Direct Addressing Table의 줄임말이다. 

배열에 어떤 종류의 알파벳이 있는지 찾는 프로그램 작성

#include <iostream>
using namespace std;
char vect[7] = "ADBFAD";
int direct[32];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i=0; i<6; i++)
    {
        direct[vect[i]-'A'] = 1;
    }
    for(int i=0;  i<32; i++)
    {
        if(direct[i] == 1)
            cout << char(i+65) << " find \n";
    }
    return 0;
}

 

이제 존재하는 것 뿐만 아니라, 갯수를 센다면 같은 원리로 1을 계속 더하면 된다.

#include <iostream>
using namespace std;
char vect[7] = "ADBFAD";
int direct[32];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i=0; i<6; i++)
    {
        direct[vect[i]-'A']++;
    }
    for(int i=0;  i<32; i++)
    {
        if(direct[i] >= 1)
            cout << char(i+65) << " find : " << direct[i] << '\n';
    }
    return 0;
}