이 진 트 리 옮 겨 다 니 기 (앞 순서 와 뒤 순 서 를 알 고 있 습 니 다. 중간 순서 로 옮 겨 다 니 는 가능 한 시퀀스 수 를 찾 습 니 다)

제목 설명 Description
    우 리 는 모두 이 진 트 리 의 앞 순서, 중간 순서, 뒤 순 서 를 잘 알 고 있 습 니 다. 데이터 구조 에서 이런 문 제 를 자주 제기 합 니 다. 이 진 트 리 의 앞 순서 와 중간 순 서 를 알 고 있 습 니 다. 그 뒤의 순 서 를 찾 습 니 다. 이에 따라 이 진 트 리 의 뒤 순서 와 중간 순 서 를 알 고 있 습 니 다. 당신 도 그의 앞 순 서 를 구 할 수 있 습 니 다.그러나 이 진 트 리 의 앞 순서 와 뒤 순 서 를 정 했 지만 그 순서 가 반복 되 는 순 서 를 확정 할 수 없습니다. 다음 그림 과 같은 이 진 트 리 몇 그루 를 고려 하 십시오.
 
    모든 이 두 갈래 나 무 는 같은 앞 순서 와 뒤 순 서 를 가지 고 있 지만 중간 순 서 는 다르다.
입력 설명 Input Description
    파일 을 입력 하면 총 2 줄 입 니 다. 첫 번 째 줄 은 이 트 리 의 앞 순 서 를 옮 겨 다 니 는 결 과 를 표시 하고 두 번 째 줄 은 이 트 리 의 뒤 순 서 를 옮 겨 다 니 는 결 과 를 표시 합 니 다.입력 한 문자 집합 은 {a - z} 이 며 길 이 는 26 을 초과 하지 않 습 니 다.
출력 설명 Output Description
    출력 파일 은 긴 정 수 를 초과 하지 않 는 정수 만 포함 하고 가능 한 중간 순 서 를 반복 하 는 시퀀스 의 총 수 를 표시 합 니 다.
샘플 입력 Sample Input
abc
cba
샘플 출력 Sample Output
4
문제 풀이 방향:
    이 문 제 를 풀기 전에 먼저 기초 지식 을 좀 알 아야 한다.
    앞 순서 옮 겨 다 니 기: 뿌리 결산 점 --- > 왼쪽 나무 --- > 오른쪽 나무
    왼쪽 하위 트 리 근점 ---> 오른쪽 나무
    왼쪽 하위 트 리 - > 오른쪽 하위 트 리 ---> 근점
    이상 의 앞 뒤 순 서 를 통 해 알 수 있 듯 이 앞 뒤 순 서 를 옮 겨 다 니 는 것 과 뒤 순 서 를 옮 겨 다 니 는 상황 에서 중간 순 서 는 유일 하 게 확정 되 지 않 습 니 다.그리고 중 서 를 옮 겨 다 니 는 불확실 성 은 한 노드 (한 쪽 나무 만) 의 좌우 서브 트 리 의 불확실 성에 의 해 결정 된다.예 를 들 어 앞 순 서 는 ab 를 옮 겨 다 니 고 뒤 순 서 는 ba 를 옮 겨 다 니 며 a 는 뿌리 이 고 b 는 서브 트 리 이 며 중간 순 서 는 b 가 왼쪽 서브 트 리 라면 중간 순 서 는 ba 이다.b 가 오른쪽 하위 트 리 라면 중간 순 서 는 ab 입 니 다.그래서 이런 노드 가 n 개 일 때 중간 순서 가 옮 겨 다 닐 가능성 은 2 ^ n 입 니 다.
    그러면 문 제 는 이런 노드 의 수량 을 확정 하면상례 와 같이 하나의 규칙 을 총 결 해 낼 수 있다.앞 순 서 는 ab 이 고 뒤 순 서 는 ba 입 니 다. 이때 b 가 왼쪽 나무 인지 오른쪽 나무 인지 확인 할 수 없 으 면 특수 한 노드 가 생 깁 니 다.그래서 규칙 은 (이때 a, b 는 각각 앞 순 서 를 옮 겨 다 니 는 문자열): a [i] = b [j] 일 때 a [i + 1] = b [j - 1] 는 특수 한 노드 를 만 드 는 것 이다.
코드 는 다음 과 같 습 니 다:

#include

#include

#define M 30

int count=0;

int power(int ans);

int main()

{

	 char a[M],b[M];
	
	 int i=0,j=0;
	 
	 int lengthA=0,lengthB=0;
	
	 gets(a);
	
	 gets(b);
	
	 lengthA=strlen(a),lengthB=strlen(b);
	
	 for(i=0;i=0) sum*=2;
	return sum;
}