学步园

一开始用map记录映射dfs，结果TLE了。然后发现第一个串中只会出现’a’-‘z’，所以可以以这26个字母用一个vis记录该字母是否被映射，再记录该字母映射下的字符串就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s1[20],s2[60];
int n,n1,n2;
int vis[26];
char map[26][5];
int judge(int a,char* c)
{
    for(int i=0;i<strlen(c);i++)
        if(s2[a+i]!=c[i]) return 0;
    return 1;
}
int dfs(int i,int j)
{
    if(i==n1&&j==n2) return 1;
    if(i==n1) return 0;
    if(vis[s1[i]-'a'])
    {
        if(j+strlen(map[s1[i]-'a'])<=n2&&judge(j,map[s1[i]-'a']))
        {
            if(dfs(i+1,j+strlen(map[s1[i]-'a']))) return 1;
            else return 0;
        }
        else return 0;
    }
    int flag=0;
    for(int k=1;k<=n;k++) if(j+k<=n2)
    {
        vis[s1[i]-'a']=1;
        for(int t=0;t<k;t++)
            map[s1[i]-'a'][t]=s2[j+t];
        map[s1[i]-'a'][k]='\0';
        if(dfs(i+1,j+k)) flag=1;
        vis[s1[i]-'a']=0;
    }
    return flag;
}
int main()
{
    freopen("in.txt","r",stdin);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>s1>>s2;
        n1=strlen(s1);
        n2=strlen(s2);
        memset(vis,0,sizeof(vis));
        cout<<dfs(0,0)<<endl;
    }
    return 0;
}