Codeforces 852G Bathroom terminal

对于每一个Pattern,建立一个Trie树。在遍历Pattern串构建Trie树时,用一个数组来保存哨兵指针,用以标记当前状态。初始时数组中只有一个指针,指向根节点。如果遇到了a~e(以a为例),则将在当前(所有)的哨兵节点下均增加一个合法的a的输入,用每一个新的a子节点代替当前结点作为哨兵;如果遇到了?,则扩充当前的哨兵数组:为当前的哨兵数组中的每一个哨兵节点添加a、b、c、d、e五个合法输入,将新的子节点全部添加进哨兵数组。此时哨兵数组由6个部分组成:原来的哨兵节点、新的a子节点、新的b子节点……新的e子节点。

匹配时一个一个字符进行匹配即可。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _852G
{
    class Program
    {
        class Trie
        {
            private bool Matched = false;
            private Trie[] next = new Trie[5];

            public void SetMatched()
            {
                Matched = true;
            }

            public bool IsMatched()
            {
                return Matched;
            }

            private int GetIndex(char c)
            {
                return c - 'a';
            }

            public Trie AddChar(char c)
            {
                return GetOrAdd(GetIndex(c));
            }

            public Trie GetNext(char c)
            {
                return next[GetIndex(c)];
            }

            private Trie GetOrAdd(int index)
            {
                if (next[index] == null)
                {
                    next[index] = new Trie();
                }
                return next[index];
            }
        }

        static bool Match(string words, Trie pattern)
        {
            for (int i = 0; i < words.Length; i++)
            {
                pattern = pattern.GetNext(words[i]);
                if (pattern == null)
                {
                    return false;
                }
            }
            return pattern.IsMatched();
        }

        static void Main(string[] args)
        {
            int[] MN = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int M = MN[0];
            int N = MN[1];
            string[] words = new string[M];

            for (int i = 0; i < M; i++)
            {
                words[i] = Console.ReadLine();
            }

            for (int i = 0; i < N; i++)
            {
                string pattern = Console.ReadLine();
                Trie trie = new Trie();
                List<Trie> pivot = new List<Trie>();
                pivot.Add(trie);
                for (int j = 0; j < pattern.Length; j++)
                {
                    if (pattern[j] != '?')
                    {
                        pivot = pivot.Select(p => p.AddChar(pattern[j])).ToList();
                    }
                    else
                    {
                        List<Trie> q = new List<Trie>();
                        for (int c = 0; c < 5; c++)
                        {
                            q.AddRange(pivot.Select(p => p.AddChar((char)('a' + c))).ToList());
                        }
                        pivot.AddRange(q);
                    }
                }
                pivot.ForEach(p => p.SetMatched());

                int sum = 0;

                for (int j = 0; j < M; j++)
                {
                    if (Match(words[j], trie))
                    {
                        sum++;
                    }
                }

                Console.WriteLine(sum);
            }

        }
    }
}

Default Comments (0)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Disqus Comments (0)

dontpanic92-cn