这道题当初卡了我不知道多少遍,每次动手想作一下CSP认证的第三道题,都从这道题开始,但每次都被卡住。直接是连题意都有点读不懂,可是读懂了以后就会发现,这道题除了特别繁琐以外,好像也没用到什么很难的算法。c++
借鉴了这位大佬的思路:https://blog.csdn.net/xbb224007/article/details/79962425?utm_source=blogxgwz0算法
我没发现比这个还简洁的代码,因此就学了一下这个思路,比较容易理解。数组
对这道题,我实际上是无从下手的。究其缘由,在于:1.字符串匹配的题目作的太少了,没作几道。2.不太会stringstream流操做,因此对复杂的字符串操做不够灵活。3.数据结构没想出来,不知道用什么来存这么多的字符串。数据结构
题目大意是这样的,给出一连串匹配规则,以及一连串待匹配字符串。对每一个待匹配字符串,要拿每个规则匹配它,若是匹配成功,就输出这个规则名称,以及成功匹配的参数部分(即用题中的str、int、path成功匹配的部分,其余的成功匹配不输出);若是对全部规则都不匹配,就输出404。函数
先开一个一维字符串数组,存放全部原始规则,再开一个二维字符数组,存放每个原始规则被'/'拆分后的部分。再开一个一维整型数组,存放每一条原始规则拆分后的部分数,再开一个记号数组,标记每一条原始数组是否为'/'结尾。spa
以后开一个二重循环,对每一条待匹配语句都对每一条规则进行比较,若是有一个成立就跳出。匹配函数是一个模块。对每个语句的匹配,都要拆分开来,一部分一部分匹配,这须要一个拆分函数;对
下面是代码,部分关键地方有注释。其实很显然,难就难在对字符串的拆分和匹配上了,数据结构想不出来,拆分不会,这题就是0分了。code
程序中有不少小细节,个中巧妙之处,须要细细体会。blog
#include <bits/stdc++.h> #define N 105 using namespace std; string lim[N],lims[N][N],limname[N]; //lim是第i个规则字符串,lims是第i个规则字符串的拆分,limname是对应字符串的名字 string now,nows[N]; //nows是当前被检索字符串的拆分 bool isop[N],iso; //isop判断规则末尾有无斜杠,iso判断地址末尾有无斜杠 int limcnt[N],nowcnt; //limcnt计数规则的拆分后项数,nowcnt计数当前被检索字符串的拆分后项数 void stcut(string ori,string cut[],bool& is,int&num); bool match(int j,int nc,string& a); string isnum(string s); int main() { int n,m; cin>>n>>m; for (int i=0;i<n;i++) { cin>>lim[i]>>limname[i]; stcut(lim[i],lims[i],isop[i],limcnt[i]); } for (int i=0;i<m;i++) { cin>>now;iso=0; //注意此处将iso置0 stcut(now,nows,iso,nowcnt); string ans; int f=0; for (int j=0;j<n;j++) { if (match(j,nowcnt,ans)) { string ss=limname[j]+ans; cout<<ss<<endl; f=1;break; } } if (f==0) cout<<404<<endl; } return 0; } //nows是当前字符串,j是当前的断定模块序号,nc是当前字符串切分后的项数,a是可能的跟在标签后面的答案字符串 bool match(int j,int nc,string& a) { a=""; int p1=0,p2=0; while (p1<nc&&p2<limcnt[j]) { if (nows[p1]==lims[j][p2]) ; else if (lims[j][p2]=="<int>") { string st=isnum(nows[p1]); if (st=="") return 0; else a+=' '+st; } else if (lims[j][p2]=="<path>") { a+=' '+nows[p1++]; while (p1<nc) a+='/'+nows[p1++]; if (iso) a+='/'; return 1; } else if (lims[j][p2]=="<str>") a+=' '+nows[p1]; else return 0; p1++,p2++; } if (p1<nc||p2<limcnt[j]) return 0; if (isop[j]^iso) return 0; return 1; } //ori是原始字符串,cut是切割后的分块,is是判断最后有无'/',num是切分后的项数 void stcut(string ori,string cut[],bool& is,int& num){ int len=ori.size(); string ss; num=0; if (ori[len-1]=='/') is=1; for (int i=0;i<(int)ori.size();i++) if (ori[i]=='/') ori[i]=' '; stringstream in(ori); while (in>>ss) cut[num++]=ss;; } string isnum(string s) { string ans=""; int ok=0; for (int i=0;i<(int)s.size();i++) { if (s[i]<'0'||s[i]>'9') return ""; else if (ok||(s[i]>'0'&&s[i]<='9')) ans+=s[i],ok=1; } return ans; }