[UVA] 175 - Keywords

題意:
給幾個題材(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