深度優先搜尋之困難的串

1. 問題描述：

如果一個字元串包含兩個相鄰的重複子串，則稱它為容易的串，其他串稱為困難的串

如:BB，ABCDACABCAB,ABCDABCD都是容易的，A, AB, ABA, D, DC, ABDAB, CBABCBA都是困難的。

輸入正整數n, L 輸出由前L個字元(大寫英文字母)組成的，字典序第n小的困難的串。

例如，當L=3時，前7個困難的串分别為:

A, AB, ABA, ABAC, ABACA, ABACAB, ABACABA

n指定為4的話,輸出ABAC

2. 因為是要進行試探的結果那麼我們這裡使用dfs來進行解決，其中這道題目涉及到兩個難點，一是維持字典序的問題，另外一個是如何判斷是否為困難的串的問題

① 維持字典序的話我們能夠盡量往深的地方搜尋，就盡量往深的地方搜尋，而盡量不去搜尋它的橫的地方，即能不搜尋它的兄弟盡量不搜尋它的兄弟

是以這裡當把目前的字元加進來的時候，就永遠不會退回去去搜尋它的平行狀态即不搜尋它的兄弟元素了，就沒有了平行狀态了，是以此時就不需要進行回溯了，因為它不受到平行狀态的影響了

② 二是要解決如何判斷是否為困難的串的問題，這裡使用到了一種技巧就是不用去搜尋它的所有的情況，即不用相鄰一個一個進行判斷，相鄰兩個兩個字元進行判斷...我們考慮到這裡傳進方法來的本來就是一個困難的串，是以并不需要像上面這樣進行搜尋情況的判斷，隻需要考慮目前加入的字元與其他字元組合起來再與相鄰長度的字元串進行比較來看一下是否相同，如果相同那麼加進來這個字元之後變成了容易的串，那麼這個字元應該舍棄

3. 具體的代碼如下：

import java.util.Scanner;
public class Main{
	static int n;
	static int count;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int L = sc.nextInt();
		dfs("", L);
		sc.close();
	}
	
	private static void dfs(String s, int L) {
		for(char c = 'A'; c < 'A' + L; c++){
			if(isHard(s, c)){
				String prefix = s + c; 
				System.out.println(prefix);
				count++;
				if(count == n){
					System.exit(0);
				}
				dfs(prefix, L);
			}	
		}
	}

	private static boolean isHard(String prefix, char c){
		int count = 0;
		for(int i = prefix.length() - 1; i >= 0; i -= 2){
			String s1 = prefix.substring(i, i + count + 1);
		    String s2 = prefix.substring(i + count + 1) + c;
		    if(s1.equals(s2)) return false;
		    count++;
		}
		      return true;
	}
}
           

 判斷是否為困難的串有是有傳入的并不知道是什麼樣子的串，那麼就需要對它所有的情況進行搜尋

4. 下面是具體判斷是否是困難的串的方法：

判斷的代碼如下：（調試的時候在截取完字元串之後使用輸出語句檢視輸出的内容來判斷代碼判斷是否正确）

import java.util.Scanner;
public class Main{
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		n = s.length();
		isHard(s);
		sc.close();
	}

	private static void isHard(String s){
		boolean flag = true;
		for(int index = 1; index <= n / 2; index++){
			for(int j = n; j - 2 * index >= 0; j -= index){
				String prefix2 = s.substring(j - index, j);
				String prefix1 = s.substring(j - 2 * index, j - index);
				//System.out.println(prefix1 + " " + prefix2);
				if(prefix1.equals(prefix2)){
					System.out.println("不是一個困難的串");
					flag = false;
					break;
				}
			}
				if(flag == false){
					break;
				}
		}
				if(flag){
					System.out.println("是一個困難的串");
				}
	}	
}