AhoCorasick

using System;
using System.Collections.Generic;

public class AhoCorasick
{
    public static List<int> SearchOccurrences(string text)
    {
        int n = text.Length;
        List<int> pi = new List<int>(n);
        for (int i = 0; i < n; i++)
        {
            pi.Add(0);
        }

        for (int i = 1; i < n; i++)
        {
            int j = pi[i - 1];
            while (j > 0 && text[i] != text[j])
            {
                j = pi[j - 1];
            }
            if (text[i] == text[j])
            {
                j++;
            }
            pi[i] = j;
        }

        return pi;
    }

    public static void Main()
    {
        string text = Console.ReadLine();
        int numPatterns = int.Parse(Console.ReadLine());

        for (int i = 0; i < numPatterns; i++)
        {
            string pattern = Console.ReadLine();
            string temp = pattern + "#" + text;
            List<int> pi = SearchOccurrences(temp);
            for (int j = pattern.Length; j < pi.Count; j++)
            {
                if (pi[j] == pattern.Length)
                {
                    Console.Write(j - 2 * pattern.Length + 1 + " ");
                }
            }
        }

        Console.WriteLine();
    }
}