2022NOIonline测试题第三题字符串(string)

请大家看一看，不知道该使用队列还是使用什么算法，代码也不知道该如何去优化？
#include
#include
#include
using namespace std;
string a[400];
queue q;
string left(string a){
string b="";
for(int i=1;i<a.length();i++){
b+=a[i];
}
return b;
}
string right(string a){
string b="";
for(int i=0;i<a.length()-1;i++){
b+=a[i];
}
return b;
}
int main() {
int t,n,m,x,y,flag;
long long num=0;
string s,str,tmp;
cin>>t;
while(t--){
cin>>n>>m>>s>>str;
x=0,tmp="",flag=0;
for(int i=0;i<n;i++){//10--01
if(s[i]!='-'){
if(flag==1){
x++;
flag=0;
}
a[x]+=s[i];
}else{
if(x==0&&a[x]==""){
a[x]="";
}else{
a[++x]="-";
}
flag=1;
}
}
/*
10 - 01 -
0 1 2 3
/
int k=1;
q.push(a[0]);
for(int i=1;i<=x;i++){
if(a[i]!="-"){
for(int j=1;j<=k;j++){
tmp=q.front();
tmp+=a[i];
q.push(tmp);
q.pop();
}
}else{
for(int j=1;j<=k;j++){
tmp=q.front();
q.push(left(tmp));
q.push(right(tmp));
q.pop();
}
k=2;
}
}
while(!q.empty()){
tmp=q.front();
if(tmp==str){
num++;
}
q.pop();
}
cout<<num%(1000000007)<<endl;
}
return 0;
}

用递归来做,参考

#include <iostream>
#include <string>
using namespace std;
int n, m;
string s, str, q;
void pft(int k,long long &num)
{
    char c;
    string st;
    if (k>=n)
    {
        if (q==str)
            num++;
        return;
    }
    if (s[k]=='-')
    {
        c = q.back();
        q.pop_back();
        pft(k+1,num);
        q.push_back(c);
        st = q.substr(0,1);
        q.erase(0,1);
        pft(k+1,num);
        q.insert(0,st);
    } else {
        q.push_back(s[k]);
        pft(k+1,num);
        q.pop_back();
    }
}

int main()
{
    int t;
    long long num;
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> s >> str;
        num = 0;
        pft(0,num);
        cout << num % (1000000007) << endl;
    }
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!