学步园

问题：新单词接龙。

规则：

（1）单词变换：单词Wi添加一个字母，删除一个字母或修改一个字母可以得到单词Wi+1;

（2）字典序接龙：W1,W2,W3....Wn，满足字典序。

将所有单词存在hash表或者Trie树中，然后判断一个单词能否通过变换得到另一个单词，如果能够，则连边。得到的是一个DAG图，做图上最长路径即可。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack> 
using namespace std;

const int maxn = 100003;
const int maxd = 20;

struct Edge
{
	int v, next;
}edge[maxn*4];

int cnt;
int first[maxn];

void read_graph(int u, int v)
{
	edge[cnt].v = v;
	edge[cnt].next = first[u], first[u] = cnt++;
}

typedef char State[17];

typedef unsigned long UL;

State st[maxn];

struct Hash
{
	int first[maxn];
	int next[maxn];
	
	void init() { memset(first, -1, sizeof(first)); }
	int ELFhash(char *key)  
	{  
    	UL h = 0;  
    	while(*key)
    	{  
        	h = (h<<4) + *key++;  
        	UL g = h & 0xf0000000L;  
        	if(g) h ^= g>>24;  
        	h &= ~g;  
    	}  
    	return h%maxn;
	}  


	int insert(int s)
	{
		int h = ELFhash(st[s]);
		next[s] = first[h];
		first[h] = s;
	}

	int find(char *s)
	{
		int h = ELFhash(s);
		for(int u = first[h]; ~u; u = next[u])
		{
			if(strcmp(s, st[u]) == 0) return u;
		}
		return -1;
	}
}ha;

void change(char *s1, int u)
{
	char s2[maxd];
	int len = strlen(s1);
	memcpy(s2, s1, sizeof(s1));
	for(int i = 0; i < len; i++)
	{
		for(char j = 'a'; j <= 'z'; j++)
		{
			char t = s2[i];
			s2[i] = j;
			int v = ha.find(s2);
			if(v >= 0) read_graph(u, v);
			s2[i] = t;
		}
	}
}

void add(char *s1, int u)
{
	char s2[maxd];
	int len = strlen(s1);
	
	for(int i = 0; i <= len; i++)
	{
		for(char j = 'a'; j <= 'z'; j++)
		{
			memcpy(s2, s1, sizeof(s1));
			for(int k = len; k >= i; k--)
			{
				s2[k+1] = s2[k];
			}
			s2[i] = j;
			int v = ha.find(s2);
			if(v >= 0) read_graph(u, v);
		}
	}
}

void del(char *s1, int u)
{
	char s2[maxd];
	int len = strlen(s1);
	
	for(int i = 0, j = 0; i < len; i++)
	{
		int k = 0;
		for(int j = 0; j < len; j++) if(i != j) s2[k++] = s1[j];
		s2[k] = '\0';
		int v = ha.find(s2);
		if(v >= 0) read_graph(u, v);
	}
}

void init()
{
	cnt = 0;
	memset(first, -1, sizeof(first));
}

int d[maxn];

bool vis[maxn];

int dp(int u)
{
	int &ans = d[u];
	if(vis[u]) return ans;
	vis[u] = 1;
	ans = 1;
	for(int e = first[u]; e != -1; e = edge[e].next)
	{
		int v = edge[e].v;
		if(strcmp(st[u], st[v]) < 0) ans = max(ans, dp(v)+1);
	}
	return ans;
}

int n;

int main()
{
	char s1[maxd], s2[maxd];
	n = 0;
	init();
	ha.init();
	while(~scanf("%s", st[n]) && strcmp(st[n], "@END@"))
	{
		ha.insert(n);
		n++;
	}
	for(int i = 0; i < n; i++)
	{
		change(st[i], i);
		del(st[i], i);
		add(st[i], i);
	}
	
	int ans = 0;
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < n; i++) ans = max(ans, dp(i));
	printf("%d\n", ans);
	system("pause");
}