攻击jsp网站,网店设计流程,app营销推广方案,网页制作在线生成题目描述
已知有两个字串 A,B 及一组字串变换的规则#xff08;至多 6 个规则#xff09;#xff0c;形如#xff1a;
A1→B1。A2→B2。
规则的含义为#xff1a;在 A 中的子串 A1 可以变换为 B1#xff0c;A2 可以变换为 B2⋯。
例如#xff1a;Aa…题目描述
已知有两个字串 A,B 及一组字串变换的规则至多 6 个规则形如
A1→B1。A2→B2。
规则的含义为在 A 中的子串 A1 可以变换为 B1A2 可以变换为 B2⋯。
例如AabcdBxyz
变换规则为
abc→xuud→yy→yz。
则此时A 可以经过一系列的变换变为 B其变换的过程为
abcd→xud→xy→xyz。
共进行了 3 次变换使得 A 变换为 B。
输入格式
第一行有两个字符串 A,B。
接下来若干行每行有两个字符串 Ai,Bi表示一条变换规则。
输出格式
若在 10 步包含 10 步以内能将 A 变换为 B则输出最少的变换步数否则输出 NO ANSWER!。
输入输出样例
输入 #1
abcd xyz
abc xu
ud y
y yz输出 #1
3说明/提示
对于 100% 数据保证所有字符串长度的上限为 20。
【题目来源】
NOIP 2002 提高组第二题
解题思路
采用广度搜索字符串匹配采用朴素模式匹配也可以需要注意的是主串可能有多个子串匹配成功在bfs中都需要加入列队别看只有6个规则列队数组却比较大不然RE等你
AC代码
#includestdio.h
#includestring.h
struct nb {//储存变化规则char s[23];//变化前char h[23];//变化后
}e[8];
struct linknode {//列队char g[23];//串int s;//步数
}link[2110000];
int main()
{int k 1;char a[23], b[23];scanf(%s %s, a, b); //输入起始串和终止串while (scanf(%s %s, e[k].s, e[k].h)!EOF)//输入规则k;int hard 1, tail 2, flag 0;strcpy(link[1].g, a); link[1].s 0;//起始串入队while (hard tail link[hard].s 10){for (int i 1; i k; i)//列举所有变化规则{int x 0, y 0;int p strlen(link[hard].g);int q strlen(e[i].s);while (x p)//继续寻找主串后面是否有匹配的{while (x p y q)//朴素模式匹配{if (link[hard].g[x] e[i].s[y]){x; y;}else{x x - y 1;y 0;}}if (y q)//yq代表匹配成功{int mm 0;//入队操作for (int j 0; j x - y; j)link[tail].g[mm] link[hard].g[j];int hj strlen(e[i].h);for (int j 0; j hj; j)link[tail].g[mm] e[i].h[j];for (int j x; j p; j)link[tail].g[mm] link[hard].g[j];link[tail].g[mm] \0; link[tail].s link[hard].s 1;if (strcmp(link[tail].g, b) 0)//如果找到终点串结束{flag 1;break;}tail;}y 0;}if (flag 1)break;}if (flag 1)break;hard;//一个点广搜结束进行下一个}if (flag 1)//找到终点串{if (link[tail].s 10)printf(%d, link[tail].s);elseprintf(NO ANSWER!);}else//没找到终点串printf(NO ANSWER!);return 0;
}
