第二题-塔子哥的编译原理实验【KMP】

本题的模式串可以展开，使用栈来模拟即可，每次一个(放入栈中对应的位置以及前面的数量，每次)弹出栈顶元素，然后将栈顶元素的数量乘以当前的字符串加上栈顶元素的前面的字符串加入到模式串中即可。

需要注意有可能模式串非常长，所以中间需要判断是否已经超过了匹配串的长度，超过则直接返回。

有了模式串和匹配串之后，就可以使用KMP算法来进行匹配了。

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5+100;

char ta[N],a[N],b[N];
int Next[N];
//getNext求解长度为len的字符串s的next数组
void getNext(char s[],int len)
{
	int j=-1;
	Next[0]=-1;                //初始化j=next[0]=-1;
//	cout<<next[0]<<endl;
	for(int i=1;i<len;i++)     //求解next[1]~next[len-1]
	{
		while(j!=-1&&s[i]!=s[j+1])
		{
			j=Next[j];      //反复令j=next[j];
		}  //直到j回退到-1，或是s[i]==s[j+1]
		if(s[i]==s[j+1])
			j++;  //则next[i]=j+1,先令j指向这个位置
		Next[i]=j;    //令next[i]=j
	}
}

//KMP算法，判断pattern是否是text的子串
int KMP(char text[],char pattern[])
{
	int n=strlen(text),m=strlen(pattern);   //求字符串长度
	getNext(pattern,m);     //计算pattern的next数组
	int j=-1;    //初始化j为-1，表示当前还没有任意一位被匹配
	for(int i=0;i<n;i++)  
	{     //这里i是从0开始
//		while(j!=-1&&text[i]!=pattern[j+1])   //试图匹配text[i]
//			j=Next[j];   //不断回退，直到j回到-1或text[i]==pattern[j+1]
//		if(text[i]==pattern[j+1])
//			j++;        //text[i]与pattern[j+1]匹配成功，令j加1
		while(j!=-1&&((pattern[j+1]=='N'&&!(text[i]>='0'&&text[i]<='9'))||(pattern[j+1]=='A'&&(text[i]>='0'&&text[i]<='9'))))   //试图匹配text[i]
			j=Next[j];   //不断回退，直到j回到-1或text[i]==pattern[j+1]
		if((pattern[j+1]=='N'&&(text[i]>='0'&&text[i]<='9'))||(pattern[j+1]=='A'&&!(text[i]>='0'&&text[i]<='9')))
			j++;        //text[i]与pattern[j+1]匹配成功，令j加1
		if(j==m-1)    //pattern完全匹配，说明pattern是text的子串
			return i;
	}
	return -1;   //执行完text还没匹配成功，说明pattern不是text的子串
}
signed main(){
	scanf("%s%s",a,b);
	int alen=strlen(a);
	deque<int> st; 
	int num=0;
	for(int i=0;i<alen;i++){
		if(a[i]>='0'&&a[i]<='9'){
			num=num*10+(int)(a[i]-'0');
		}else if(a[i]=='('){
			st.push_back(num);
			num=0;
		}else if(a[i]==')'){
			vector<int> p;p.clear();
			while(st.size()&&(st.back()==-1||st.back()==-2)){
				p.push_back(st.back());
				st.pop_back();
			}
			int num=st.back();st.pop_back();
//			cout<<"num:"<<num<<endl;
			reverse(p.begin(),p.end());
			for(int j=0;j<num;j++){
				for(int k=0;k<p.size();k++){
					st.push_back(p[k]);
				}
			}
		}else{
			if(a[i]=='A') st.push_back(-1);
			else st.push_back(-2);
		}
	}
	int cnt=0;
	
	while(!st.empty()){
		if(st.front()==-1)
			ta[cnt]='A';
		else
			ta[cnt]='N';
		cnt++;
		st.pop_front();
	}
//	reverse(ta,ta+cnt);
//	for(int i=0;i<strlen(ta);i++) cout<<ta[i];cout<<endl;
	int pos = KMP(b,ta);
//	cout<<pos<<endl;2(ab)
	for(int i=pos-strlen(ta)+1;i<=pos;i++) cout<<b[i];
	return 0;
}
/*
2(ab) => abab
2(av)2(ab)=>avavabab
*/