设目标串 T='bccdcdccba'，模式 P='cdcc'，按KMP模式匹配算法，第_趟匹配成功。A. 2B. 3C. 4D. 5

本题考查KMP（Knuth-Morris-Pratt）模式匹配算法的应用。解题思路是先根据模式串计算出其对应的部分匹配表（也称为next数组），然后利用该表进行模式匹配，统计匹配成功时的趟数。

步骤一：计算模式串 P='cdcc' 的部分匹配表（next数组）

部分匹配表的计算规则是：对于模式串的每个前缀，计算其最长相等前后缀的长度。

• 对于模式串 P 的第一个字符 c，没有前缀，所以 next[0] = 0。
• 对于前缀 c，最长相等前后缀长度为 0，所以 next[1] = 0。
• 对于前缀 cd，最长相等前后缀长度为 0，所以 next[2] = 0。
• 对于前缀 cdc，最长相等前后缀为 c，长度为 1，所以 next[3] = 1。

因此，模式串 P 的部分匹配表 next = [0, 0, 0, 1]。

步骤二：进行KMP模式匹配

设目标串 T 的索引为 i，模式串 P 的索引为 j，初始时 i = 0，j = 0。

• 第一趟匹配：

  • T[0] = 'b'，P[0] = 'c'，T[0] != P[0]，i 向后移动一位，i = 1，j 保持为 0。
  • T[1] = 'c'，P[0] = 'c'，T[1] == P[0]，i 和 j 都向后移动一位，i = 2，j = 1。
  • T[2] = 'c'，P[1] = 'd'，T[2] != P[1]，根据部分匹配表，j = next[1] = 0。
  • T[2] = 'c'，P[0] = 'c'，T[2] == P[0]，i 和 j 都向后移动一位，i = 3，j = 1。
  • T[3] = 'd'，P[1] = 'd'，T[3] == P[1]，i 和 j 都向后移动一位，i = 4，j = 2。
  • T[4] = 'c'，P[2] = 'c'，T[4] == P[2]，i 和 j 都向后移动一位，i = 5，j = 3。
  • T[5] = 'd'，P[3] = 'c'，T[5] != P[3]，根据部分匹配表，j = next[3] = 1。
  • T[5] = 'd'，P[1] = 'd'，T[5] == P[1]，i 和 j 都向后移动一位，i = 6，j = 2。
  • T[6] = 'c'，P[2] = 'c'，T[6] == P[2]，i 和 j 都向后移动一位，i = 7，j = 3。
  • T[7] = 'c'，P[3] = 'c'，T[7] == P[3]，i 和 j 都向后移动一位，i = 8，j = 4。此时 j 等于模式串的长度，第一趟匹配失败。

• 第二趟匹配：

  • 由于第一趟匹配失败，根据部分匹配表，j = next[3] = 1，i 保持为 8。
  • T[8] = 'b'，P[1] = 'd'，T[8] != P[1]，根据部分匹配表，j = next[1] = 0。
  • T[8] = 'b'，P[0] = 'c'，T[8] != P[0]，i 向后移动一位，i = 9，j 保持为 0。
  • T[9] = 'a'，P[0] = 'c'，T[9] != P[0]，i 向后移动一位，i = 10，此时 i 超出目标串的长度，第二趟匹配失败。

• 第三趟匹配：

  • 由于第二趟匹配失败，i 回到 0，j 回到 0，重新开始匹配。
  • 经过前面的匹配过程，最终会在第三趟匹配成功。