如题,代码如下所示。
大致的思路是,用字典树维护,对于每个节点,尝试求出在它这里进行 Tab 操作会跳到哪里(不妨称为“跳转坐标”)。具体的,对于每个节点,若它是一个指令的结尾或它的多个子节点上传跳转坐标,则该点的跳转坐标为自己;否则,“跳转坐标”记为其子节点的“跳转坐标”。
看了一眼发现自己会做直接开做,没想到调了 1.5h 还是调不出来。在这里还是告诫各位选手要懂得取舍,不然只会让自己陷入分数与心态的双重两难境地。
#include<bits/stdc++.h>
using namespace std;
const int Maxn=100000,Maxm=5000000,Maxlen=1000000,Maxp=26;
int n,m,cnt=0;
string s,nw;
struct node
{
int nt,fa,p;
bool tag;
int suf[Maxp+2];
}nums[Maxlen+10];
void dfs(int u)
{
int res=0;
for(int i=0;i<Maxp;i++)
{
if(nums[u].suf[i]==0) continue;
dfs(nums[u].suf[i]);
if(res==0) res=nums[nums[u].suf[i]].nt;
else res=u;
}
if(nums[u].tag) res=u;
nums[u].nt=res;
return;
}
void check(int u,string txt)
{
cout<<u<<" "<<txt<<":"<<endl;
cout<<nums[u].nt<<" "<<nums[u].fa<<" "<<nums[u].p<<" "<<nums[u].tag<<endl;
/*for(int i=0;i<Maxp;i++)
if(nums[u].suf[i]!=0) cout<<char(i+'a')<<" "<<nums[u].suf[i]<<endl;*/
for(int i=0;i<Maxp;i++)
if(nums[u].suf[i]!=0) check(nums[u].suf[i],txt+char(i+'a'));
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s;
int ptr=0;
for(char c:s)
{
if(nums[ptr].suf[c-'a']!=0) ptr=nums[ptr].suf[c-'a'];
else
{
cnt++;
nums[ptr].suf[c-'a']=cnt;
nums[cnt].fa=ptr;
ptr=cnt;
}
}
nums[ptr].tag=true;
nums[ptr].p=i;
}
dfs(0);
//check(0,"");
cin>>s;
int ptr=0,over=0;
for(char c:s)
{
if('a'<=c&&c<='z')
{
if(over>0||nums[ptr].suf[c-'a']==0) over++;
else ptr=nums[ptr].suf[c-'a'];
}
else if(c=='B')
{
if(over>0) over--;
else if(ptr!=0) ptr=nums[ptr].fa;
}
else if(c=='T') {if(over==0) ptr=nums[ptr].nt;}
else
{
if(over==0&&nums[ptr].tag) cout<<nums[ptr].p<<" ";
else cout<<-1<<" ";
ptr=over=0;
}
//cout<<ptr<<" "<<over<<endl;
}
return 0;
}