[SWEA-D3] 1213. String

▶문제설명

[SWEA] 1213. String

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14P0c6AAUCFAYi&categoryId=AV14P0c6AAUCFAYi&categoryType=CODE

▶Hint

---

패턴 매칭 알고리즘을 활용한다.

▶Solution

---

#include<iostream>
#include<string>
using namespace std;
 
string str, pattern;
int patternLen;
int strLen;
 
int getJumpSize(int idxS, int idxP) {
    int jump = 0, idx = 0;
    char ch = 0;
    
    while (true) 
    {
        if (str[idxS] == pattern[idxP]) {
            if (idxP == 0)
                return -1;
 
            idxS--;
            idxP--;
 
            continue;
        }
 
        ch = str[idxS];
        if ((idx = pattern.substr(0,idxP).find(ch)) != string::npos) { // 패턴내에 문자가 존재하는경우
            jump = (patternLen - 1) - idx;
        }
        else
            jump = patternLen;
 
        break;
    }
 
    return jump;
}
 
int main(int argc, char** argv)
{
    int T, idxS, idxP, jump, answer;
 
    for (int test_case = 0; test_case < 10; test_case++) {
        cin >> T;
        cin >> pattern;
        cin >> str;
 
        patternLen = pattern.length();
        strLen = str.length();
        idxS = idxP = pattern.length() - 1;
        answer = jump = 0;
 
        while (true) 
        {
            jump = getJumpSize(idxS, idxP);
        
            if (jump == -1) {
                answer++;
                jump = pattern.length();
            }
 
            idxS += jump;
 
            if (strLen - 1 < idxS)
                break;
        }
        printf("#%d %d\n", T, answer);
    }
 
    return 0;
}