1874.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1874 on 2006-03-11 at 10:49:36 */ 
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> vi;
const int MAX = 128;
const int N_MAX = 1024;

class Status {
public:
	int best, prev[2], n;
	void clear() { n = best = 0; }
	void update(int, int, int);
};
void Status::update(int t, int a, int b) {
	if(best > t) return;
	else if(best < t) n = 0;
	prev[n++] = (a<<8)|b; best = t;
}

char alice[MAX], bob[MAX], com[MAX];
string path[N_MAX];
int pn, len;
Status st[MAX][MAX];

void findPath(int, vi&);

int main()
{
	int i, j;

	while(scanf("%s %s", alice, bob) != EOF) {
		int n1 = strlen(alice), n2 = strlen(bob);
		memset(com, 0, sizeof(com)); pn = 0;
		for(i = 0; i <= n1; i++)
			for(j = 0; j <= n2; j++) {
				st[i][j].clear();
				if(i == 0 || j == 0) continue;
				else if(alice[i-1] == bob[j-1]) st[i][j].update(st[i-1][j-1].best+1, i-1, j-1);
				else {
					st[i][j].update(st[i-1][j].best, i-1, j);
					st[i][j].update(st[i][j-1].best, i, j-1);
				}
			}
		vi v; v.push_back((n1<<8)|n2);
		len = st[n1][n2].best; findPath(len, v);
		sort(path, path+pn);
		for(i = 0; i < pn; i++) printf("%s\n", path[i].c_str());
	}
	
	return 0;
}

void findPath(int step, vi& v)
{
	if(step == 0) path[pn++] = string(com, com+len);
	else {
		int i;
		bool vst[MAX][MAX] = { false };
		queue<int> Q; vi nxt[26];
		for(i = 0; i < (int)v.size(); i++) Q.push(v[i]);
		while(!Q.empty()) {
			int pa = Q.front()>>8, pb = Q.front()&127; Q.pop();
			for(i = 0; i < st[pa][pb].n; i++) {
				int ca = st[pa][pb].prev[i]>>8, cb = st[pa][pb].prev[i]&127;
				if(vst[ca][cb]) continue;
				else if(st[pa][pb].best == st[ca][cb].best) Q.push(st[pa][pb].prev[i]);
				else nxt[alice[ca]-'a'].push_back(st[pa][pb].prev[i]);
				vst[ca][cb] = true;
			}
		}
		for(i = 0; i < 26; i++)
			if(nxt[i].size() != 0) {
				com[step-1] = 'a' + i;
				findPath(step-1, nxt[i]);
			}
	}
}