困难的串（搜索）

如果一个字符串包含包含两个相邻的重复字串，则成为容易的串，否则为困难的串，例如困难的串A，AB，ABAC，ABACA,...

输入n,L,输出由前L个字符组成的，字典序第k小的困难的串。

思路和N皇后问题类似，在判断是否存在重复字串只需判断当前串的后缀，而不是所有子串。

1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int L,n,s; 5 bool flag=0; 6 char ch[10000]; 7 int judge(int s) 8 { 9 int i=s,j=s,k=1,x; 10 if(s<=1) 11 return 1; 12 else 13 { 14 while(k<=s/2) 15 { 16 int count=0; 17 j=j-1; 18 for(x=0;x<k;x++) 19 if(ch[i-x]==ch[j-x]) 20 count++; 21 if(count==k) 22 return 0; 23 k++; 24 } 25 } 26 return 1; 27 } 28 void dfs(int s) 29 { 30 int i,j,k; 31 if(flag) 32 return; 33 if(s==(n+1)) 34 { 35 for(i=1;i<=n;i++) 36 cout<<ch[i]; 37 cout<<endl; 38 flag=1; 39 return; 40 } 41 for(i=0;i<L;i++) 42 { 43 ch[s]='A'+i; 44 if(judge(s)) 45 { 46 s++; 47 dfs(s); 48 } 49 } 50 } 51 int main() 52 { 53 int i,j,k; 54 while(cin>>n>>L) 55 { 56 s=1; 57 flag=0; 58 dfs(s); 59 } 60 return 0; 61 }

 

转载于:https://www.cnblogs.com/a1225234/p/4955893.html

总结

以上是生活随笔为你收集整理的困难的串（搜索）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。