[백준 BAEKJOON] 16916번 부분 문자열

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

 

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

 

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

16916번: 부분 문자열

 

 

풀이 코드

바로 이전 포스팅에 작성한 KMP 알고리즘을 이용해서 해당 문제를 풀어보았다.

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var s = Console.ReadLine();
        var pattern = Console.ReadLine();

        Console.WriteLine(KMP(s, pattern) ? "1" : "0");
    }

    static bool KMP(string s, string pattern)
    {
        var piList = GetPi(s);

        int begin = 0;
        int match = 0;

        while(begin + match < s.Length)
        {
            if (match < pattern.Length && s[begin + match] == pattern[match])
            {
                match++;

                if (pattern.Length == match)
                {
                    return true;
                }
            }
            else
            {
                if (match == 0)
                {
                    begin++;
                }
                else
                {
                    begin += match - piList[match - 1];
                    match = piList[match - 1];
                }
            }
        }

        return false;
    }

    static List<int> GetPi(string s)
    {
        List<int> list = new List<int>();
        
        for (int i = 0; i < s.Length; i++)
        {
            list.Add(0);
        }

        int begin = 1;
        int match = 0;

        while(begin + match < s.Length)
        {
            if (s[begin + match] == s[match])
            {
                match++;
                list[begin + match - 1] = match;
            }
            else
            {
                if (match == 0)
                {
                    begin++;
                }
                else
                {
                    begin += match - list[match - 1];
                    match = list[match - 1];
                }
            }
        }

        return list;
    }
}

 

함께 보면 좋은 글

KMP 문자열 탐색 알고리즘