【Uva 11604 编码都有歧义了】

·你的目的就是要让编码有歧义，这就美妙了。

·英文题，述大意：

      给出n个模板字符串，询问是否存在一个字符串，使得用模板串（随便你用多少个）来拼凑这个串，能够至少有两种拼法。如果有，就输出“有”。

·分析：

     值得注意的是，n的范围不太大(0<n<101)。

     如果直接思考如何拼凑，那么就是一个典型的搜索枚举思想，对于这道题来说，也是一个典型的爆炸超时思想。不过，如果拥有一个好的习惯，你会不禁想到：正着不行反着来。所以，我们考虑对于一个串，把它切成几块，并使得每块都属于模板串。如果有两种切法，那么就可以输出“Yes”了。

比如这样：

·目的明确。对于一个串，我们将其切割，我们在将这样的状态重画一遍：

·玩着玩着，我们意识到：分成的小段一定是属于模板串的。所以考虑用模板串去填出大串（逆向思维已经贡献了它的全部加值，现在应该回来了）。

·分析一类简单情况，如图，我们要拼凑满足条件的大串：

·首先会拿上面两个模板串，就拼出了大串。然后你会拿下面两个模板串再来拼一个一样的大串，然后就可以输出“Yes”了。

·在反复拼凑的过程中，得到一些结论：
①每种拼法每一个位置上的字母上一样的（不要忽视）

②不同的拼法，所使用模板串时，发现只有部分重叠（相同）的模板串能够在靠近的位置，如图：

·可以看见，红串绿串有公共前缀，在不同拼法中起点相同；黄串与蓝串有公共后缀，在不同拼法中终点相同；红串与黄串的关系是：红串的一个后缀等于黄串的一个前缀，它们在不同拼法中收尾相接（部分重叠）。你可以在冥冥之中感受到，两种拼凑方式是有联系的，即这个串可能会“指导”另一个串的合成。

·神秘跳跳方法解决问题。我们用这样的顺序，来搭建这两个串：（结合上图吧）先在上面放置一个绿串，然后在模板中寻找前缀与它相同的串来搭建下面的串，于是找到了红串，将红串放置。现在红串伸出去了一截，在模板中寻找前缀与这一截相同的串，找到黄串，放在上面。现在黄串伸出去了一截，在模板串中寻找前缀与这一截相同的串，找到蓝串，放置蓝串于下方。发现没有那个伸出去一截了，也就是说，当前拼的大串，我们已经找到有两种拼法了。

·总结规律：只要还伸出去了一截，我们就永不停息，直到没有伸出的一截。说句老实话，找不到就是找不到，还是要停息的（不停息的现实意义就是超时）。

·方法：枚举两两模板串，并记录一个模板串的第i位开始，可以接上（即上文的相同）另一个串的开头（举例子就是红串的第6位开始可以接上黄串）。怎样表示关系呢？就建边把，将每一个模板串的每一位看成一个节点，然后就搭建有向边（比如红串第6位可一建一条边通向黄串第5位）。什么时候结束呢，如果从某个串i位到末尾就完全等于一个另一个模板串（就像上文黄串与蓝串的关系一样），就说明不会冒出一截了，也就是找到答案。

·代码(防水的)浮出水面：

 #include<stdio.h>

 #include<cstring>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 #define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)

 const int N=;struct E{int v,next;}e[N*];

 int T,x,n,m,len[N],sz,ID[N][],head[N*],k,over;char s[N][];bool vis[N*],can;

 void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;}

 void dfs(int u){if(can=u==over)return;vis[u]=;fo(i,head,u)if(!vis[v]){dfs(v);if(can)return;}}

 int main(){while(scanf("%d",&x),can=sz=,k=,x)

 {

     go(i,,x){scanf("%s%s",s[i]+,s[i]+);len[i]=strlen(s[i]+);

     go(j,,len[i])vis[sz]=head[ID[i][j]=++sz]=;}vis[sz+]=;

     go(a,,x){n=len[a];go(I,,n){go(b,,x){m=len[b];

         if(a==b&&I==)continue;int i=I-,j=;

         while(s[a][++i]==s[b][++j]&&i<=n&&j<=m);

         if(i>n&&j>m) ADD(ID[a][I],over);

         if(i<=n&&j>m)ADD(ID[a][I],ID[a][i]);

         if(i>n&&j<=m)ADD(ID[a][I],ID[b][j]);

     }}}

     go(i,,x){if(!vis[ID[i][]])dfs(ID[i][]);if(can)break;}

     printf("Case #%d: ",++T);puts(can?"Ambiguous.":"Not ambiguous.");

 }return ;}//Paul_Guderian

我无法忘记故乡秋末的麦地，
和南方水柳摇摆的倩影。——————汪峰《雨天的回忆》