[C#]백준 1786번: 찾기

https://www.acmicpc.net/problem/1786

1786번: 찾기

---

• 문제

---

• 문제풀이

기본적으로 KMP알고리즘을 사용해주고 패턴과 입력값이 같을때마다 count++해주고 시작 인덱스를 두번째 출력으로 찍어야하기 때문에 StringBuilder에 저장해준다.

이후 count와 StringBuilder에 저장되었던 값을 차례로 입력해준다.

 

---

• 코드 1

using System;
using System.Text;

class GFG
{
    public StringBuilder sb=new StringBuilder();
    void KMPSearch(string pat, string txt)
    {
        int M = pat.Length;
        int N = txt.Length;
        int count = 0;
        int[] lps = new int[M];
        int j = 0;


        computeLPSArray(pat, M, lps);

        int i = 0;
        while (i < N)
        {
            if (pat[j] == txt[i])
            {
                j++;
                i++;
            }
            if (j == M)
            {
                count++;
                sb.Append((i - j+1)+" ");
                j = lps[j - 1];
            }

            // mismatch after j matches
            else if (i < N && pat[j] != txt[i])
            {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
        Console.WriteLine(count);
        Console.WriteLine(sb.ToString());
    }

    void computeLPSArray(string pat, int M, int[] lps)
    {

        int len = 0;
        int i = 1;
        lps[0] = 0;


        while (i < M)
        {
            if (pat[i] == pat[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
            else
            {

                if (len != 0)
                {
                    len = lps[len - 1];


                }
                else
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }


    public static void Main()
    {
        string txt = Console.ReadLine();
        string pat = Console.ReadLine();
        new GFG().KMPSearch(pat, txt);
    }
}

 

---

• 후기

첫 플래티넘 문제 재밌다 이틀걸렸다...