【20200602程序设计思维与实践 Week15 作业】

B - ZJM 与生日礼物

题意

ZJM收到了Q老师送来的生日礼物，但是被 Q老师加密了。只有 ZJM 能够回答对Q老师的问题，Q老师才会把密码告诉 ZJM。

Q老师给了ZJM一些仅有 01组成的二进制编码串, 他问ZJM：是否存在一个串是另一个串的前缀.

思路

本题使用字典树。在基本字典树的基础上修改插入操作，使其在插入过程中检查是否访问到某一字符串的尾或插入的字符串是已存在字符串的前缀：只要有如此两种情况，则存在一个串是另一个串的前缀。

代码

#include<iostream>
#include<string.h>
using namespace std;

struct Trie{
	static const int N=1010,charset=2;
	int tot,root,child[N][charset],flag[N];
	Trie(){
		memset(child,-1,sizeof child);
		root=tot=0;
	}
	void clear(){
		memset(child,-1,sizeof child);
		root=tot=0; 
	}
	
	int insert(char* str){
		int now=root,jud=0,len=strlen(str);
		for(int i=0;i<len;i++){
			int x=str[i]-'0';
			if(child[now][x]==-1){
				child[now][x]=++tot;
				flag[now]=0;
			}else if(i==len-1||flag[child[now][x]])jud=1;
			now=child[now][x];
		}
		flag[now]=1;
		return jud;
	}
};

int main(){
	Trie Tree;
	char str[1010];
	int JDG=0;
	int cot=0;
	while(scanf("%s",str)!=EOF){
		if(str[0]=='9'){	
			Tree.clear();
			cot++;
			if(JDG)printf("Set %d is not immediately decodable\n",cot);
			else printf("Set %d is immediately decodable\n",cot);
			JDG=0;
			continue;
		}
		if(Tree.insert(str))JDG=1;
	}
}

C - ZJM 与纸条

题意

ZJM 的女朋友是一个书法家，喜欢写一些好看的英文书法。有一天 ZJM 拿到了她写的纸条，纸条上的字暗示了 ZJM 的女朋友 想给 ZJM 送生日礼物。ZJM 想知道自己收到的礼物是不是就是她送的，于是想看看自己收到的礼物在纸条中出现了多少次。

思路

本题要求在主串中找到所有与模式串匹配的子串。用暴力算法复杂度为O(nm)，所以使用了KMP算法来优化。

KMP算法的关键在于跳过必不可能成功的字符串比较以减少比较的趟数。为此，准备了Next数组，其中Next[i]表示使模式串的0~i位的K-真前缀等于K-真后缀的最大K，该数组可在线性时间内计算出来。利用Next数组，主串在于模式串失配后可以跳过已经被确保不可能匹配的子串，从而也在线性时间内完成全部的检查。

代码

#include<iostream>
#include<cstring>
using namespace std;

char P[10005],S[1000005];
int Next[10005];
int N,cot;

void get_next(const char ptr[],int len){
	Next[0]=0;
	for(int i=1,j=0;i<len;++i){
		while(j&&ptr[j]!=ptr[i])j=Next[j-1];
		if(ptr[j]==ptr[i])j++;
		Next[i]=j;
	}
}

void KMP(const char str[],const char ptr[]){
	int len1=strlen(str);
	int len2=strlen(ptr);
	int j=0;
	get_next(ptr,len2);
	for(int i=0;i<len1;i++){
		while(j&&ptr[j]!=str[i])j=Next[j-1];
		if(ptr[j]==str[i])j++;
		if(j==len2){
			cot++;
			j=Next[j-1];
		}
	}
} 


int main(){
	scanf("%d",&N);
	while(N--){
		cot=0;
		scanf("%s",P);
		scanf("%s",S);
		KMP(S,P);
		printf("%d\n",cot);
	}
}