UVA 10029 Edit Step Ladders(dp)

Problem C: Edit Step Ladders

An 
edit step
 is a transformation from one word 
x
 to another word 
y
 such that 
x
 and 
y
 are words in the dictionary, and 
x
 can be transformed to 
y
 by adding, deleting, or changing one letter. So the transformation from 
dig
 to 
dog
 or from 
dog
 to 
do
 are both edit steps. An 
edit step ladder
 is a lexicographically ordered sequence of words 
w1, w2, ... wn
 such that the transformation from 
wi
 to 
wi+1
 is an edit step for all 
i
 from 1 to 
n-1
.
For a given dictionary, you are to compute the length of the longest edit step ladder.

Input

The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line. No word exceeds 16 letters and there are no more than 25000 words in the dictionary.

Output

The output consists of a single integer, the number of words in the longest edit step ladder.

Sample Input

cat
dig
dog
fig
fin
fine
fog
log
wine

Sample Output

5

제목: 사전을 정하고 삭제를 거쳐 다른 단어로 변환할 수 있는 단어를 추가하거나 바꾸면 이 두 단어는 계단 변화로 가장 긴 계단 변화 사전을 구한다.
사고방식lis, n^2로 시간 초과했어...그리고 문제풀이를 이해하지 못해 n(logn) 방법이 있는 것을 발견했다.
단어마다 바꿀 수 있는 상황을 모두 내놓고 앞에서 2분 동안 찾아보세요. 서열 자체가 사전 서열이기 때문에 가능합니다.이렇게 하면 넘어갈 수 있어요.
코드:

#include <stdio.h>
#include <string.h>
int max(int a, int b) {return a > b ? a : b;}
int min(int a, int b) {return a < b ? a : b;}
const int N = 25555, M = 20;
char word[N][M], str[M];
int n, i, j, k, l, dp[25555], ans;

void change(char *word, char *str, char c, int wei) {
	int i;
	for (i = 0; word[i]; i ++)
		str[i] = word[i];
	str[wei] = c;
	str[i] = '\0';

}

void del(char *word, char *str, int wei) {
	int i;
	for (i = 0; i < wei; i ++)
		str[i] = word[i];
	for (i = wei + 1; word[i]; i ++)
		str[i - 1] = word[i];
	str[i - 1] = '\0';
}

void add(char *word, char *str, char c, int wei) {
	int i;
	for (i = 0; i < wei; i ++)
		str[i] = word[i];
	str[wei] = c;
	for (i = wei; word[i]; i ++)
		str[i + 1] = word[i];
	str[i + 1] = '\0';
}

void tra(char *word, char *str, char c, int wei, int flag) {
	if (flag == 0) change(word, str, c, wei);
	else if (flag == 1) del(word, str, wei);
	else add(word, str, c, wei);
}

int find(char *str, int j) {
	int i = 0;
	j --;
	while (i <= j) {
		int mid = (i + j) / 2;
		if (strcmp(word[mid], str) == 0) {
			return mid;
		}
		else if (strcmp(word[mid], str) < 0) {
			i = mid + 1;
		}
		else
			j = mid - 1;
	}
	return -1;
}

int main() {
	while (gets(word[n])) {
		n ++;
	}
	ans = 0;
	for (i = 0; i < n; i ++) {
		dp[i] = 1;
		for (k = 0; k < 3; k ++) {
			for (j = 0; word[i][j]; j ++) {
				for (l = 0; l < 26; l ++) {
					tra(word[i], str, 'a' + l, j, k);
					if (strcmp(word[i], str) < 0) break;
					int mid = find(str, i);
					if (mid >= 0) dp[i] = max(dp[i], dp[mid] + 1);
				}
			}
		}
		ans = max(ans, dp[i]);
	}
	printf("%d
", ans);
	return 0;
}