lightoj1129

maksyuki 发表于 oj 分类，标签: 字符串-Trie树

27 8月 2015

1129 - Consistency Checker

123SETI is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to travelling millions of miles signal gets distorted. Now they asked you check the consistency of their data sets. The consistency is that, no number is the prefix another number in that data set. Let's consider a data set:

5123456
123456

In this data set, numbers not consistent, because the first number is the prefix of the third one.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with an integer n (1 ≤ n ≤ 10000) denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has length from 1 to 10.

Output

For each case, print the case number and 'YES' if the list is consistent or 'NO' if it's not.

Sample Input

Output for Sample Input

2391197625999

91125426

113

12340

123440

12345

98346

Case 1: NOCase 2: YES

题目类型：Trie树

算法分析：将所有的单词插入到Trie树中，然后对于每个输入中的单词，查询其终止节点是否有后继节点即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000 + 66;

char ss[maxn][16];

struct Trie
{
    int next[maxn*10+66][10];
	int len, root;

	int newnode ()
	{
        for (int i = 0; i < 10; i++)
			next[len][i] = -1;

		len++;
		return len - 1;
	}

    void init ()
    {
        len = 0;
        root = newnode ();
    }

    void Insert (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (next[p][s[i]-'0'] == -1)
                next[p][s[i]-'0'] = newnode ();

			p = next[p][s[i]-'0'];
		}
    }

    bool Query (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (next[p][s[i]-'0'] == -1)
				return false;

			p = next[p][s[i]-'0'];
		}

		for (int i = 0; i < 10; i++)
            if (next[p][i] != -1)
				return true;

		return false;
    }
};

Trie aa;

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;

    cin >> t;

    while (t--)
	{
		cout <<"Case " << flag++ << ": ";

        aa.init ();

        int n;
        cin >>n;
        for (int i = 1; i <= n; i++)
		{
			cin >> ss[i];
			aa.Insert(ss[i]);
		}

		bool is_valid = true;
        for (int i = 1; i <= n; i++)
		{
            if (aa.Query(ss[i]))
			{
				is_valid = false;
				break;
			}
		}

		if (is_valid)
			cout << "YES" << endl;

		else
			cout << "NO" << endl;

	}
return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000 + 66;

char ss[maxn][16];

struct Trie

{

int next[maxn*10+66][10];

int len, root;

int newnode ()

{

for (int i = 0; i < 10; i++)

next[len][i] = -1;

len++;

return len - 1;

}

void init ()

{

len = 0;

root = newnode ();

}

void Insert (char *s)

{

int p = root;

for (int i = 0; s[i]; i++)

{

if (next[p][s[i]-'0'] == -1)

next[p][s[i]-'0'] = newnode ();

p = next[p][s[i]-'0'];

}

bool Query (char *s)

{

int p = root;

for (int i = 0; s[i]; i++)

{

if (next[p][s[i]-'0'] == -1)

return false;

p = next[p][s[i]-'0'];

}

for (int i = 0; i < 10; i++)

if (next[p][i] != -1)

return true;

return false;

}

};

Trie aa;

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

cin >> t;

while (t--)

{

cout <<"Case " << flag++ << ": ";

aa.init ();

int n;

cin >>n;

for (int i = 1; i <= n; i++)

{

cin >> ss[i];

aa.Insert(ss[i]);

}

bool is_valid = true;

for (int i = 1; i <= n; i++)

{

if (aa.Query(ss[i]))

{

is_valid = false;

break;

}

if (is_valid)

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

lightoj1127

lightoj1131

超客的水墨烟雨

lightoj1129

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30