[11478] 서로 다른 부분 문자열의 개수

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

• 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

• 첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

생각

부분집합을 구하는 문제다.
각 원소를 포함하거나 포함하지 않거나 하기 때문에, 이진트리가 생각나기도 한다.
문자열 리스트에 모든 부분집합을 저장한 뒤, Count를 출력한다.

인 줄 알았는데, 각 원소의 배치는 바뀌지 않은 채로 해야한다.
그러니까,
ababc면 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc 에서 중복을 제외해야 하는 것이다...
길이는 1000 이하니까, 딱히 for문을 써도 상관은 없을 듯..

1) 이중포문을 사용하여 각 문자로부터 +1, +2, +3... 최대 문자열의 마지막 부분의 char 까지 stringbuilder 에 추가한다.
2) 해당 sb를 list에 추가한다.
3) 반복하면 a일때, b일때, 2번째a일때.. 식으로 리스트에 부분문자열이 추가된다.
4) 중복을 제거하기 위해 LinQ의 Distinct() 사용

이런식

처음 코드

using System.Text;

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            char[] data = input.ReadLine().ToCharArray();
            List<string> list = new();

            for(int i = 0; i < data.Length; i++)
            {
                StringBuilder sb = new StringBuilder();
                sb.Append(data[i]);
                list.Add(sb.ToString());
                for(int j = i+1 ; j < data.Length; j++)
                {
                    sb.Append(data[j]);
                    list.Add(sb.ToString());
                }
            }

            IEnumerable<string> result = list.Distinct();
            print.WriteLine(result.Count());
        }
    }
}

검색 안하고 스스로의 힘으로 이뤄내다 ㄷㄷ