หา Substrings ทั้งหมดของสตริงใน C#

การสร้าง Substrings ทั้งหมด (All Substrings) ของสตริง ใช้ Nested Loop กับ Substring Method

อัลกอริทึม: ทุกความยาว × ทุกตำแหน่งเริ่มต้น

using System;

public class Demo
{
    public static void Main()
    {
        string str = "pqrz";

        for (int len = 1; len <= str.Length; len++)        // ความยาว 1 ถึง N
        {
            for (int start = 0; start <= str.Length - len; start++) // ตำแหน่งเริ่มต้น
            {
                string substr = str.Substring(start, len);
                Console.WriteLine(substr);
            }
        }
    }
}

ผลลัพธ์สำหรับ "pqrz"

p
q
r
z
pq
qr
rz
pqr
qrz
pqrz

จำนวน Substrings ทั้งหมด

สำหรับสตริงยาว N: N × (N + 1) / 2 Substrings

• N=4 → 10 Substrings
• N=100 → 5,050 Substrings
• N=1000 → 500,500 Substrings

Optimized Versions

LINQ Version

using System.Linq;

var allSubstrings = Enumerable.Range(1, str.Length)
    .SelectMany(len => Enumerable.Range(0, str.Length - len + 1)
        .Select(start => str.Substring(start, len)));

StringBuilder Version (Less Allocations)

public static IEnumerable GetAllSubstrings(StringBuilder sb)
{
    string str = sb.ToString();
    for (int len = 1; len <= str.Length; len++)
    {
        for (int start = 0; start <= str.Length - len; start++)
        {
            yield return str.Substring(start, len);
        }
    }
}

Span-based (Zero Allocation - .NET Core 2.1+)

public static IEnumerable> GetAllSubstringsSpan(ReadOnlySpan span)
{
    for (int len = 1; len <= span.Length; len++)
    {
        for (int start = 0; start <= span.Length - len; start++)
        {
            yield return span.Slice(start, len); // No Allocation!
        }
    }
}

// ใช้งาน
foreach (var substr in GetAllSubstringsSpan("pqrz".AsSpan()))
{
    Console.WriteLine(substr.ToString()); // Allocate เฉพาะตอน Print
}

Unique Substrings Only (Distinct)

var unique = new HashSet();
for (int len = 1; len <= str.Length; len++)
    for (int start = 0; start <= str.Length - len; start++)
        unique.Add(str.Substring(start, len));

// หรือ LINQ
var unique = Enumerable.Range(1, str.Length)
    .SelectMany(len => Enumerable.Range(0, str.Length - len + 1)
        .Select(start => str.Substring(start, len)))
    .Distinct()
    .ToList();

Applications

• String Algorithms: Suffix Array, Suffix Tree, LCP Array
• Bioinformatics: DNA Sequence Analysis
• Text Search: Naive Pattern Matching
• Compression: LZ77, LZ78 Dictionary Building
• NLP: N-gram Generation

⚠️ Memory Warning

สตริงยาว 10,000 ตัวอักษร → ~50 ล้าน Substrings → OutOfMemoryException

ใช้ Streaming (yield return) หรือ Span แทนการ Materialize ทั้งหมด