本文共 2102 字，大约阅读时间需要 7 分钟。

Problem Description

Input

Output

Sample Input

abcde a3aaaaaa  aa#

Sample Output

03

题意：找到可能剪出的最多的小饰条数目。

思路：本题可以完全套用KMP。找到的匹配可能有很多个，而且可能重合，本题中需要找到能够分开的子串，即剪出不同的小饰条。这个问题很简单，直接在一次完全匹配后，让 j = 0 匹配永不回溯的 i 的新位置即可。

代码如下：

#include 
   
    using namespace std;const int maxn = 1010;char s[maxn], p[maxn];int nextArr[maxn]; int slen, plen;namespace kmp1 {
   	void getNext() {
    //预先计算nextArr[],用于在失配的情况下得到回溯的位置 		nextArr[0] = 0, nextArr[1] = 0;		for (int i = 1; i < plen; ++i) {
   			int j = nextArr[i];			while (j && p[i] != p[j]) j = nextArr[j];			nextArr[i + 1] = (p[i] == p[j] ? j + 1 : 0);		}	}	int kmp() {
   											//在s中找到p 		if (slen < plen) return 0;			getNext();		int j = 0, ans = 0; //last=-1;					//last指向上次匹配的末尾位置 		for (int i = 0; i < slen; ++i) {
   		 		//匹配s和p的每个字符 			while (j && s[i] != p[j]) j = nextArr[j];	//失配后用nextArr[]找j的回溯位置 			if (s[i] == p[j]) ++j;						//当前位置的字符匹配,继续 			if (j >= plen) {
   							//完全匹配 				++ans;				j = 0;			}			/*			if (i - last >= plen) {						//判断新的匹配和上个匹配能否分开 				++ans;						last = i;			}			*/		}		return ans;	}}namespace kmp2 {
   	void getNext() {
   		nextArr[0] = -1, nextArr[1] = 0;		int pos = 2, cn = 0;		while (pos < plen) {
   			if (p[pos - 1] == p[cn]) nextArr[pos++] = ++cn;			else if (cn > 0) cn = nextArr[cn];					else nextArr[pos++] = cn;		}	}	int kmp() {
   		if (slen < plen) return 0;		getNext();		int i = 0, j = 0, ans = 0;		while (i < slen && j < plen) {
   			if (s[i] == p[j]) ++i, ++j;			else if (nextArr[j] != -1) j = nextArr[j];	//j != 0			else ++i;				//else if (nextArr[j] == -1) ++i;			//else j = nextArr[j];			if (j >= plen) {
   	//匹配完了一次 				++ans;				j = 0;			}		}		return ans;	}} int main() {
    	while (~scanf("%s", s)) {
   		if (s[0] == '#') break;		scanf("%s", p);		slen = strlen(s), plen = strlen(p);		//printf("%d\n", kmp1::kmp());		printf("%d\n", kmp2::kmp());	}    return 0;}
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108244851 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！