首页 > 代码库 > poj 4089:电话号码
poj 4089:电话号码
poj 4089:电话号码
题目
给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。
每个测试样例的第一行是一个整数n，1 ≤ n ≤ 10000，其后n行每行是一个不超过10位的电话号码。
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
NO YES
解题方案
这个题目子问题
（1）字符串完全匹配
我想到的是用map去做，对于每一个电话，其长度为length，然后我们可以求出length个前子串，然后去匹配，如果能匹配到，那么电话有冲突，否则没有
data.txt
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
代码
#include <iostream>
#include <map>
#include <fstream>
#include <string>
using namespace std;
void read_data();
bool main_solution( string * data,int n );
int main()
{
read_data();
system( "pause" );
return 0;
}
bool main_solution( string * data,int n )
{
map<string,bool> mymap ;
string substr ;
for(int i=0;i<n;i++)
{
for(int j=1;j <= data[i].length();j++)
{
substr = data[i].substr(0,j) ;
if( mymap.find(substr) != mymap.end() )
{
return false;
}
}
mymap.insert( make_pair( data[i] , true ));
}
return true;
}
void read_data()
{
ifstream reader;
reader.open("data.txt");
int t ;
string * data;
reader>>t;
for(int j=0;j<t;j++)
{
int n ;
reader>>n ;
data = http://www.mamicode.com/new string[n];>
poj 4089:电话号码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。