KMP吼啊!
by Soledad_S @ 2019-10-08 19:04:01
刚会OI就切这题%%%
by Provicy @ 2019-10-08 19:10:17
%%%
by 亚由亚由 @ 2019-10-08 19:11:08
@[_DXL_](/space/show?uid=98618) @[tlafd](/space/show?uid=110857) Help 喵呜qaq
by 可耐の小可耐 @ 2019-10-08 19:12:35
Fixed Half
```cpp
#include<bits/stdc++.h>
#define reg register
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
class change
{
public:
string from,to;
}c[1000005];
int tot;
string a,b;
map<string,int>used;
inline int isok(reg string s,reg int x)
{
reg int tmp=s.length();
// cout<<s<<" "<<x<<endl;
for(reg int i=0;i<=tmp;i++)
{
// cout<<tmp<<" "<<x<<" "<<s.substr(i,c[x].from.length())<<" "<<c[x].from<<endl;
if(s.substr(i,c[x].from.length())==c[x].from)
{
return i+1;
}
}
return 0;
}
inline void bfs()
{
queue<string>q;
q.push(a);
used[a]=0;
while(!q.empty())
{
reg string now=q.front();
q.pop();
// cout<<now<<endl;
if(used[now])continue;
if(now==b)
{
cout<<used[now];
exit(0);
}
for(reg int i=1;i<=tot;i++)
{
reg int iter=isok(now,i);
// cout<<iter<<endl;
if(iter)
{
iter--;
reg string tmp=now.substr(0,iter)+c[i].to+now.substr(iter+c[i].from.length(),now.length()-iter-c[i].from.length());
// cout<<i<<" "<<c[i].from<<" "<<c[i].to<<endl;
// cout<<tmp<<endl;
q.push(tmp);
used[tmp]=used[now]+1;
}
}
}
cout<<"NO ANSWER!";
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin>>a>>b;
while(tot++,cin>>c[tot].from>>c[tot].to);
tot--;
bfs();
// cout<<tot<<endl;
}
```
by liuyifan @ 2019-10-08 19:39:45
这是啥题目???
by 520Enterprise @ 2019-10-08 19:41:36
~~先证明你是妹子(关注点错~~
by _H1kar1 @ 2019-10-08 19:47:00
Fixed 80pts:
```cpp
#include<bits/stdc++.h>
#define reg register
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
class change
{
public:
string from,to;
}c[1000005];
int tot;
string a,b;
map<string,int>de,used;
inline int isok(reg string s,reg int x)
{
reg int tmp=s.length();
// cout<<s<<" "<<x<<endl;
for(reg int i=0;i<=tmp;i++)
{
// cout<<tmp<<" "<<x<<" "<<s.substr(i,c[x].from.length())<<" "<<c[x].from<<endl;
if(s.substr(i,c[x].from.length())==c[x].from)
{
return i+1;
}
}
return 0;
}
inline void bfs()
{
queue<string>q;
q.push(a);
used[a]=0;
while(!q.empty())
{
reg string now=q.front();
q.pop();
if(used[now])continue;
used[now]=1;
if(now==b)
{
cout<<de[now];
exit(0);
}
for(reg int i=1;i<=tot;i++)
{
reg int iter=isok(now,i);
if(iter)
{
iter--;
reg string tmp=now.substr(0,iter)+c[i].to+now.substr(iter+c[i].from.length(),now.length()-iter-c[i].from.length());
q.push(tmp);
de[tmp]=de[now]+1;
}
}
}
cout<<"NO ANSWER!";
}
int main()
{
cin>>a>>b;
while(tot++,cin>>c[tot].from>>c[tot].to);
tot--;
bfs();
return 0;
}
```
感谢大奆奆
by 可耐の小可耐 @ 2019-10-08 19:54:07
@[tlafd](/space/show?uid=110857)
by 可耐の小可耐 @ 2019-10-08 19:54:21
%%%
by 哲纸神偷_悉令 @ 2019-11-11 07:44:07