首页 > 代码库 > 构造字符串。。
构造字符串。。
构造字串
生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时
‘a b c b a’满足条件
‘a b c b c’不满足条件
INPUT：
两个整数N,P；N<=10，P<=26；
5 3
OUTPUT：
所有满足条件的字串的方案总数
30
思路：
一道典型的dfs。但是是字符串。如样例：B C=B C所以不符合条件。每添加一个，就要判断是否有重复。如果有return；
如何判断？
1 if(s1.size()%2==0)2 {3 for(int j=2;j<=s1.size()/2;j++)4 {5 x=s1.substr(s1.size()-j+1,j-1);x+=i;6 y=s1.substr(s1.size()-2*j+1,j);7 if(x==y) {f=0; break;}8 }9 }
但是，位数不够呢？
1 if(s1.size()>2) 2 { 3 if(s1.size()%2==0) 4 { 5 for(int j=2;j<=s1.size()/2;j++) 6 { 7 x=s1.substr(s1.size()-j+1,j-1);x+=i; 8 y=s1.substr(s1.size()-2*j+1,j); 9 if(x==y) {f=0; break;}10 }11 }12 else13 {14 for(int j=2;j<=s1.size()/2+1;j++)15 {16 x=s1.substr(s1.size()-j+1,j-1);17 x+=i;18 y=s1.substr(s1.size()-2*j+1,j);19 if(x==y)20 {f=0; break;}21 }22 }23 }
cpp：
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<iomanip> 8 #include<queue> 9 using namespace std;10 string s1,x,y;11 int n,p,sum=0;12 void dfs(string s1)13 {14 if(s1.size()==n) {sum++; return;}15 for(char i=‘a‘;i<‘a‘+p;i++)16 {17 if(i==s1[s1.size()-1]) continue;18 bool f=1;19 if(s1.size()>2)20 {21 if(s1.size()%2==0)22 {23 for(int j=2;j<=s1.size()/2;j++)24 {25 x=s1.substr(s1.size()-j+1,j-1);x+=i;26 y=s1.substr(s1.size()-2*j+1,j);27 if(x==y) {f=0; break;}28 }29 }30 else31 {32 for(int j=2;j<=s1.size()/2+1;j++)33 {34 x=s1.substr(s1.size()-j+1,j-1);35 x+=i;36 y=s1.substr(s1.size()-2*j+1,j);37 if(x==y)38 {f=0; break;}39 }40 }41 }42 if(f==1) dfs(s1+i);43 }44 }45 int main()46 {47 48 //freopen("a.in","r",stdin);49 //freopen("a.out","w",stdout);50 cin>>n>>p;51 for(char i=‘a‘;i<‘a‘+p;i++)52 {53 s1.clear();54 dfs(s1+i);55 }56 cout<<sum<<endl;57 return 0;58 }
P.S(cpp MADE BY MHZ)
构造字符串。。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。