UVa 12785 Emacs Plugin-平芜编程栈

题目描述

Emacs\texttt{Emacs}Emacs是一个以插件扩展为特点的文本编辑器。本题中，我们需要实现一个高效的字符串匹配算法，用于匹配带有通配符的模式。

文本ttt是由小写字母组成的字符串。模式ppp是由小写字母和通配符'*'组成的字符串。模式ppp匹配文本ttt当且仅当ppp可以作为子串出现在ttt中，并且ppp中的每个'*'可以匹配ttt中的任意子串（包括空串）。

例如，对于文本t=t =t="hehelloyou"：

模式"hel*"匹配，因为'*'可以匹配"loyo"或空串
模式"*o*e"不匹配
模式"e*o"匹配，例如'*'匹配"lloy"

输入包含多个测试用例，每个测试用例先给出模式数量nnn，然后是文本ttt，接着是nnn行模式。对每个模式输出"yes"或"no"表示是否匹配。

问题分析

模式的结构特点

通配符'*'的特殊之处在于它可以匹配任意长度的字符串，这与传统的单字符通配符'?'完全不同。这种通配符实际上类似于正则表达式中的.*，但这里的'*'是独立的符号，不是量词。

观察模式的构成，我们可以发现：

模式被'*'分割成若干段，每段都是纯字母组成的字符串
连续多个'*'等价于一个'*'，因为'*'已经可以匹配任意长度
模式开头或结尾的'*'表示可以匹配文本开头之前或结尾之后的内容（即可以部分匹配）

匹配的本质

匹配过程实际上是在文本中寻找模式中各段按顺序出现的位置。例如模式"ab*c"要求：

先找到"ab"
然后中间可以有任意字符（由'*'匹配）
最后找到"c"

但要注意，模式作为整体必须是文本的一个连续子串，只是'*'部分可以匹配任意内容。也就是说，整个模式对应文本中的一个连续区间，其中固定部分必须精确匹配，通配符部分可以任意。

关键观察

假设我们将模式按'*'分割得到段序列s1,s2,...,sks_1, s_2, ..., s_ks1,s2,...,sk，其中某些段可能是空串（对应连续'*'或首尾'*'）。那么匹配过程可以描述为：

在文本中找到一个位置pos1pos_1pos1，使得s1s_1s1从pos1pos_1pos1开始匹配
然后在pos1+∣s1∣pos_1 + |s_1|pos1+∣s1∣之后的位置找到s2s_2s2第一次出现的位置pos2pos_2pos2
以此类推，直到所有段都匹配完成

这里的关键是：每个非空段只需要找到第一次出现的位置即可。为什么？因为如果我们将某个段匹配得更靠后，那么留给后面段的空间就更少，反而可能降低匹配成功的可能性。而匹配得更靠前，则后面有更多空间，更有可能匹配成功。因此贪心策略（每次都匹配最早可能的位置）是正确的。

解题思路

算法设计

基于上述分析，我们可以设计如下算法：

模式预处理：将模式按'*'分割成段
- 遍历模式的每个字符
- 遇到'*'时将当前累积的字符串作为一个段保存，并清空累积
- 将最后一段也加入段列表
贪心匹配：
- 初始化当前搜索位置pos=0pos = 0pos=0
- 遍历每个段segsegseg：
  - 如果segsegseg是空串（对应连续'*'或首尾'*'），直接跳过
  - 否则在文本中从pospospos开始查找segsegseg第一次出现的位置foundfoundfound
  - 如果找不到，匹配失败
  - 如果找到，更新pos=found+∣seg∣pos = found + |seg|pos=found+∣seg∣（从该段末尾之后继续搜索）
结果判断：所有段都成功匹配则输出"yes"，否则输出"no"

正确性证明

贪心策略的正确性：

假设对于某个段sis_isi，存在两个可能的位置aaa和bbb都可以匹配，且a<ba < ba<b。如果我们选择bbb而不是aaa，那么：

选择aaa后，剩余文本长度至少为∣t∣−(a+∣si∣)|t| - (a + |s_i|)∣t∣−(a+∣si∣)
选择bbb后，剩余文本长度为∣t∣−(b+∣si∣)|t| - (b + |s_i|)∣t∣−(b+∣si∣)

由于a<ba < ba<b，选择aaa后的剩余文本更长，因此更容易匹配后续的段。如果选择bbb能匹配成功，那么选择aaa也一定能匹配成功（因为后续段只需要在更长的文本中按顺序出现）。反之则不成立。因此，贪心地选择最早出现位置不会错过任何可行解。

复杂度分析

基础版本：每个模式匹配时，最多进行O(∣p∣)O(|p|)O(∣p∣)次查找（段的数量）。每次查找使用string::find\texttt{string::find}string::find最坏情况O(∣t∣⋅∣seg∣)O(|t| \cdot |seg|)O(∣t∣⋅∣seg∣)，但实际运行效率尚可。
优化版本：使用后缀自动机，预处理O(∣t∣⋅∣Σ∣)O(|t| \cdot |\Sigma|)O(∣t∣⋅∣Σ∣)，每个模式匹配O(∣p∣)O(|p|)O(∣p∣)，总复杂度O(∣t∣+∑∣pi∣)O(|t| + \sum |p_i|)O(∣t∣+∑∣pi∣)。

基础实现（string::find\texttt{string::find}string::find版本）

// Emacs Plugin// UVa ID: 12785// Verdict: Accepted// Submission Date: 2026-02-27// UVa Run Time: 0.630s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 判断模式 p 是否匹配文本 tboolmatch(conststring&t,conststring&p){vector<string>segments;// 存储按 '*' 分割后的段string cur;// 当前正在累积的段// 将模式按 '*' 分割for(charc:p){if(c=='*'){segments.push_back(cur);// 将当前段加入列表cur.clear();// 清空当前段}else{cur+=c;// 累积字符}}segments.push_back(cur);// 将最后一段加入列表intpos=0;// 当前在文本中的搜索起始位置// 依次匹配每个非空段for(conststring&seg:segments){if(seg.empty())continue;// 空段（对应连续 * 或首尾 *）直接跳过size_t found=t.find(seg,pos);// 从 pos 开始查找 seg 第一次出现的位置if(found==string::npos)returnfalse;// 找不到则匹配失败pos=found+seg.size();// 更新搜索位置到该段末尾之后}returntrue;// 所有段都匹配成功}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cin>>n){// 处理多个测试用例string t;cin>>t;// 读入文本while(n--){string p;cin>>p;// 读入模式cout<<(match(t,p)?"yes":"no")<<'\n';}}return0;}

优化实现（后缀自动机版本）

后缀自动机简介

后缀自动机（Suffix Automaton\texttt{Suffix Automaton}Suffix Automaton，SAM\texttt{SAM}SAM）是一种能够接受一个字符串的所有子串的最小DFA\texttt{DFA}DFA。它具有以下优秀性质：

可以在O(∣t∣)O(|t|)O(∣t∣)时间内构建
可以在O(∣p∣)O(|p|)O(∣p∣)时间内检查ppp是否是ttt的子串
可以求出ppp在ttt中第一次出现的位置

利用这些性质，我们可以将每个模式的匹配时间从O(∣t∣⋅∣p∣)O(|t| \cdot |p|)O(∣t∣⋅∣p∣)优化到O(∣p∣)O(|p|)O(∣p∣)，与文本长度无关！

优化实现

// Emacs Plugin// UVa ID: 12785// Verdict: Accepted// Submission Date: 2026-02-27// UVa Run Time: 0.070s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structSuffixAutomaton{structState{intlen,link;intnext[26];intfirstPos;// 该状态对应子串第一次出现的位置（结束位置）State(){len=0;link=-1;memset(next,-1,sizeof(next));firstPos=0;}};vector<State>st;intlast;SuffixAutomaton(){st.clear();st.push_back(State());last=0;}// 扩展一个字符voidextend(charc){intcurr=st.size();st.push_back(State());st[curr].len=st[last].len+1;st[curr].firstPos=st[curr].len-1;// 记录当前状态对应子串的结束位置intp=last;while(p!=-1&&st[p].next[c-'a']==-1){st[p].next[c-'a']=curr;p=st[p].link;}if(p==-1){st[curr].link=0;}else{intq=st[p].next[c-'a'];if(st[p].len+1==st[q].len){st[curr].link=q;}else{intclone=st.size();st.push_back(st[q]);st[clone].len=st[p].len+1;// clone 的 firstPos 保持不变，因为它是 q 的克隆while(p!=-1&&st[p].next[c-'a']==q){st[p].next[c-'a']=clone;p=st[p].link;}st[q].link=clone;st[curr].link=clone;}}last=curr;}// 查找字符串 s 在文本中第一次出现的位置（起始位置）intfindFirstPos(conststring&s){intstate=0;for(charch:s){intc=ch-'a';if(st[state].next[c]==-1)return-1;state=st[state].next[c];}// state 对应所有以 s 为后缀的子串// 其中最短的子串（长度为 |s|）的结束位置就是 firstPos// 因此起始位置 = firstPos - |s| + 1returnst[state].firstPos-s.length()+1;}};// 判断模式 p 是否匹配文本 t，使用后缀自动机优化boolmatch(conststring&t,conststring&p,SuffixAutomaton&sam){vector<string>segments;string cur;// 将模式按 '*' 分割for(charc:p){if(c=='*'){segments.push_back(cur);cur.clear();}else{cur+=c;}}segments.push_back(cur);intpos=0;// 当前在文本中的搜索起始位置for(conststring&seg:segments){if(seg.empty())continue;// 空段直接跳过// 使用 SAM 查找 seg 在文本中的第一次出现位置intfound=sam.findFirstPos(seg);if(found==-1)returnfalse;// 不是子串，匹配失败// 特殊情况：如果找到的位置在 pos 之前，说明 seg 在 pos 之前出现过// 我们需要找到在 pos 之后的位置if(found<pos){// 简单回退到 string::find 处理这种情况// 这种情况在贪心匹配中很少发生，因为每次我们都将 pos 向后移动size_t nxt=t.find(seg,pos);if(nxt==string::npos)returnfalse;pos=nxt+seg.size();}else{pos=found+seg.size();}}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cin>>n){string t;cin>>t;// 构建文本的后缀自动机SuffixAutomaton sam;for(charc:t)sam.extend(c);while(n--){string p;cin>>p;cout<<(match(t,p,sam)?"yes":"no")<<'\n';}}return0;}

两种实现的性能对比

实现版本	时间复杂度	空间复杂度	实际运行时间
string::find\texttt{string::find}string::find版本	O(n⋅∣t∣⋅∣p∣)O(n \cdot \|t\| \cdot \|p\|)O(n⋅∣t∣⋅∣p∣)最坏	O(∣p∣)O(\|p\|)O(∣p∣)	620620620ms\texttt{ms}ms
后缀自动机版本	O(∣t∣+∑∣pi∣)O(\|t\| + \sum \|p_i\|)O(∣t∣+∑∣pi∣)	O(∣t∣⋅∣Σ∣)O(\|t\| \cdot \|\Sigma\|)O(∣t∣⋅∣Σ∣)	909090ms\texttt{ms}ms