题解 P1019 【单词接龙】

卑鄙的我 · 2019-03-21 21:15:14 · 题解

女士们先生们 你们直到rfind（）函数吗？？？？ 逆向查找嘻嘻嘻 诺 神器呀有木有 第一次发题解 求过

#include<bits/stdc++.h>
#include<algorithm>
#define M 45
using namespace std;
string s[M];
bool vis[M];
int n,ans=0;
string Plus(string a,string b)
{
    int j=0,i=a.rfind(b[0]);//重头戏 
    for(;a[i]==b[j]&&i<a.length()&&j<b.length();i++,j++) ;
    if(i!=a.length()) return " ";
    return a+b.substr(j,b.length()-j);
}
void deepfs(string a)
{
    int l=a.length();
    ans=max(ans, l);
    for(int i=1;i<=n;i++)
    if(vis[i]==0)
    {
        vis[i]=1;
        string t=s[i];
        string temp=Plus(a,t);
        if(temp!=" ")   deepfs(temp);
        vis[i]=0;
    }
}
int main()
{
    cin>>n;
    n<<=1;
    for(int i=1;i<=n;i+=2)
    {
        cin>>s[i];
        s[i+1]=s[i];
    }
    cin>>s[0];
    deepfs(s[0]);
    cout<<ans;
}