題意:
給幾個題材(profile)，每個題材都有2個以上的單字，
再給定幾個標題(title)，每個標題可能有用到某個題材的單字，
。單字每個字母皆視為小寫
。不是字母都略過
例如:
(Mis)-Conceptions == misconceptions
Metaphor in 1984, Concepts == metaphor in concepts
問:每個題材有被哪些標題取用兩個單字以上，且兩單字中間穿插的字串數在限制內
範例輸入
P: 0 rock art
P: 3 concepts conceptions
P: 1 art rock metaphor concepts
T: Rock Art of the Maori|
T: Jazz and Rock - Art Brubeck and Elvis Presley|
T: Don't Rock --- the Boat as Metaphor in 1984, Concepts
and (Mis)-Conceptions of an Art Historian.|
T: Carved in Rock, The Art and Craft of making promises
believable when your `phone bills have gone
through the roof|
#
P表示profile，數字表示被取用的兩個單字間有多少個其他單字穿插
T表示Title，最後以字元'|'表示結束這個title輸入
字元 # 為結束測資輸入
範例輸出
1: 1,2
2:
3: 1,2,3,4
1: 1,2表示
profile1有被title1 和title2取用2個單字以上，
且兩個單字間沒有其他單字穿插，
title1: Rock Art of the Maori|
title2: Jazz and Rock - Art Brubeck and Elvis Presley|
Rock和Art間的'-'字元不是字母所以略過
2: 表示
profile2的單字都沒有被任何title取用2個單字以上
3: 1,2,3,4表示
profile3的單字有被title1 和 title2 和 title3 和 title4取用2個單字以上，
且兩個單字間最多只有1個單字穿插
title1:
Rock Art of the Maori|
title2: Jazz and
Rock -
Art Brubeck and Elvis Presley|
title3: Don't Rock --- the Boat as
Metaphor in 1984,
Concepts
and (Mis)-Conceptions of an Art Historian.|
title4: Carved in
Rock, The
Art and Craft of making promises
believable when your `phone bills have gone
through the roof|
注意!
P1: 0 apple banana apple
P2: 0 apple banana
T1: apple apple只有P1符合，P2不符合(P2只有一顆apple不夠)
--------------------------------------------------
方法:
先做預處理，將每個字串做編號，
要判斷第j個title是否有用到第i個profile的兩個單字以上，
就是title[j]中的每個單字哪些是profile[i]有的，先做記號，
只要任兩個相鄰記號小於profile[i]的限制距離，
表示profile[i]有被title[j]取用到。
具體作法可以找到一個profile[i]的單字就先把profile[i]的那個單字erase，
避免重複取，最後找完再復原。
**************************************************
/* 20150927
* hanting
* UVa 175 - Keywords
* C++
*/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> //find
using namespace std;
vector<string> store;
map<string,int> Map;
int ID(string str)//為字串做編號
{
if(Map.count(str)) return Map[str];
else
{
store.push_back(str);
return Map[str]=store.size()-1;
}
}
void normalize(string &str)//將不是字母的字元去掉
{
string tmp="";
for(int i=0;i<str.size();i++)
{
if(isalpha(str[i])) tmp+=tolower(str[i]);
}
str=tmp;
}
vector<int> Distance(51);
vector<int> profile[51];
vector<int> title[51];
bool Find(int i,int id)//在第i個 profile 可以找到編號id
{
vector<int>::iterator it=find(profile[i].begin(),profile[i].end(),id);
if(it!=profile[i].end())
{
profile[i].erase(it);
return true;
}
return false;
}
bool Selected(int i,int j)//第i個 profile 的字串有被第j個 Title選到，
{
int last=-1,cur=-10000;
for(int k=0;k<title[j].size();k++) //第j個 title的第k個字串
{
if(last>=0 and cur>=0 and title[j][k]==title[j][cur])
{
cur=k;
}
if(Find(i,title[j][k]))
{
last=cur;
cur=k;
if((cur-last)<=Distance[i]+1) return true;
else if(last>=0) profile[i].push_back(title[j][last]);
}
}
return false;
}
int main()
{
string str;
int Pidx=1;
int Tidx=1;
while(cin>>str and str[0]!='#')//讀P或T
{
if(str[0]=='P')
{
int dis;
cin>>dis;
Distance[Pidx]=dis;
while(cin>>str)
{
profile[Pidx].push_back(ID(str));
if(cin.get()=='\n') break;
}
Pidx++;
}
else//if(str[0]=='T')
{
while(cin>>str)
{
bool terminate=str[str.size()-1]=='|';
normalize(str);
if(str.size()==0) continue;
title[Tidx].push_back(ID(str));
if(terminate) break;
}
Tidx++;
}
}/*end of input*/
vector<int> ans[51];
for(int i=1;i<Pidx;i++)
{
for(int j=1;j<Tidx;j++)
{
vector<int> tmp(profile[i].begin(),profile[i].end());
if(Selected(i,j)) ans[i].push_back(j);
profile[i]=tmp;
}
}
for(int i=1;i<Pidx;i++)
{
cout<<i<<": ";
for(int j=0;j+1<ans[i].size();j++)
{
cout<<ans[i][j]<<",";
}
if(ans[i].size()) cout<<ans[i].back();
cout<<endl;
}
return 0;
}
--------------------------------------------------
input.txt
output:
1: 1,2,3
2: 1,2,3
