Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

....

Posted by 3013216046 at 2014-08-11 15:00:26 on Problem 2001
ke chi de zhan dai ma
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define maxn 1001
using namespace std;
char st[maxn][21], res[maxn][21];
class Trie {
	public:
		Trie *next[26];
		int flag;
		Trie() {
            for (int i = 0; i < 26; i++)
                next[i] = 0; flag = 0;
		}
		void build() {
			root = new Trie;
		}
		void insert(char *st) {
			int ans, len;
			Trie *p, *q;
			p = root;
			len = strlen(st);
			for (int i = 0; i < len; i++) {
				ans = st[i] - 'a';
				if (p -> next[ans] == NULL)
                    p -> next[ans] = new Trie;
                p = p -> next[ans]; p -> flag++;
			}
		}
		void find(char *st, char *res) {
			int len, ans;
			Trie* p;
			p = root;
			len = strlen(st);
			for (int i = 0; i < len; i++) {
				ans = st[i] - 'a';
				p = p -> next[ans];
				res[i] = st[i];
				if (p -> flag == 1) {
					res[++i] = '\0'; return;
				}
			}
		}
	private:
		Trie *root;
} Ans;
int main() {
	int n = 0;
	Ans.build();
	while (~scanf("%s", st[n])) {
		//if (st[n][0] == '.') break;
		Ans.insert(st[n]); n++;
	}
	for (int i = 0; i < n; i++)
		Ans.find(st[i], res[i]);
	for (int i = 0; i < n; i++)
		printf("%s %s\n", st[i], res[i]);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator