算法思路

给定一个 UW语法，计算其生成的语言中不同字符串的数量。若数量超过 $1000$，则输出 "Too many."。

1. 输入处理

   • 初始字符串存储在 x 中，并去除引号后存入集合 a 和队列 f。
   • 替换规则存储在二维数组 ma 中，其中 ma[i][0] 表示被替换的子串，ma[i][1] 表示替换后的子串。
   • 检查是否存在 自递归规则（如 "A"->"AA"），若存在则可能导致无限生成字符串，此时设置 flag=1。

2. 广度优先搜索（BFS）生成语言

   • 从初始字符串开始，遍历所有可能的替换规则。
   • 每次替换后，检查新字符串是否已存在于集合 a 中，若不存在则加入队列 f 和集合 a。
   • 如果生成的字符串数量超过 $1000$，则终止循环。

3. 输出结果

   • 若存在自递归规则或生成字符串数量超过 $1000$，输出 "Too many."。
   • 否则，输出集合 a 的大小，即不同字符串的数量。

关键点

• BFS 遍历：确保所有可能的替换组合都被探索。
• 去重处理：使用 set<string> a 存储已生成的字符串，避免重复计数。
• 终止条件：当生成字符串数量超过 $1000$ 或队列为空时终止。

边界情况

• 若替换规则导致无限生成（如 "A"->"AA"），输出 "Too many."。
• 若生成字符串超过 $1000$ 个，同样输出 "Too many."。

#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
string x,s;
set <string> a;
vector <string> f;
string ma[10000][3];
int len,i,t,tt;
int main()
{
	cin>>x;
	x.erase(x.begin());
	x.erase(x.end()-1);
	a.insert(x);
	f.push_back(x);
	len=0;
	int flag=0;
	while (cin>>x)
	{
		for (i=1;!(x[i+1]=='-'&& x[i+2]=='>');i++) ma[len][0]+=x[i];
		for (i+=4;i<x.length()-1;i++) ma[len][1]+=x[i];
		if (ma[len][1].find(ma[len][0])!=string::npos&& ma[len][1]!=ma[len][0]) flag=1;
		len++;
	}
	while (!flag)
	{
		x=f.front();f.erase(f.begin());
		for (i=0;i<len;i++)
		{
			t=x.find(ma[i][0]);
			while (t!=string::npos&&a.size()<=1000)
			{
				s=x;
				s.replace(t,ma[i][0].length(),ma[i][1]);
				tt=a.size();
				a.insert(s);
				if (tt<a.size()) f.push_back(s);
				t=x.find(ma[i][0],t+1);
			}
		}
		if (f.empty()||a.size()>1000) break;
	}
	if (a.size()>1000||flag) printf("Too many.\n");
	else printf("%d\n",a.size());
}