ACM试题1159 回文词.pptVIP

1159 回文词 报告人：李鑫 问题描述： 回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。次题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。 示例: 比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。 注：此问题区分大小写 数学描述： 对于一个串S=a1a2…an，求最小的m，使得存在一个串S’=b1b2…bm+n满足S为S’的一个子串（可不连续），并且bi=bm+n-i+1(i=1…m+n)。 分析： 设S ’各个字符中不为S中字符的字符位置集为X 。故 是不可能同时成立的。所以可以把S中的字符分成两类A，B： A：S’中与此字符对称的字符出现在S’-S中 B：S’中与此字符对称的字符出现在S中 比如把Ab3bd扩充成 d A b 3 b A d（红色的字母是添加的） 1 2 3 4 5 6 7 位置2，7的对称位置的字符不属于S， 故A={2, 7} 位置3，4，5的对称位置的字符属于S， 故B={3, 4, 5} 分析续： 有以下结论： |A|+|B|=|S|=n |A|=|X| B是回文词且B是S的子串 |X|=|A|=n-|B|，问题转化为求S的最大回文子串B。 算法设计： 已知S=a1a2…an 设T=c1c2…cn =an…a2 a1 设L(i,j)表示a1a2…ai和c1c2…cj的最长公共子序列的长度。 则有下面的结论： 算法设计： max|B|= max { 2*max(L(i,n-i)), 2*max(L(i,n-1-i))+1 } 其中L(i,j)可以用如下递推公式得到： 更容易想到的算法： 令c (i,j)表示将子串aiai+1…aj变成回文词的最小添加字符数。则这此问题就是要求c(1,n)。 c(i,j)满足如下递推关系： 以上两种算法的复杂度 空间复杂度O(n) 时间复杂度O(n2) * * *