求搜索相邻单词的算法

问题描述：
定义结构体struct WORD
{
  string word; //单词
  int [100]; //在文章中的位置，每个单词长度不等
  int wordFreq; //单词在文章中出现的次数
};
例如：
  我；（0，11，20，90，120）；5
  爱；（1，21，121，200，300）；5
  你；（2；22；80，301）；4
目标：
找出所有相邻的词组，如：我爱你（0，1，2；20，21，22）；我爱（0，1；20，21；120，121）；爱你（1，2；21，22；300，301）。
请求您帮忙给出一个算法。如能提供较详细的C++代码，本人感激不尽！
万分感谢！

/*
前提假设所有的页码已经是递增序列，如果没有此限定，自己排序即可

  输入 
  3 //代表3个单词
  我
  5 //代表5个pos
  0 11 20 90 120
  爱
  5
  1 21 121 200 300
  你
  4
  2 22 80 30

  主要思路按照索引依次填入相应位置，相邻的话紧挨着，不相邻中间插入隔断符号以节省空间
  完成后顺序扫描即可
*/
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
using namespace std;

typedef struct WORD{
string word;
int pos[100];
int wordFreq;
}WORD;

class Essay{
public:
Essay(int n,WORD* w):wordNum(n),words(w){
essay.empty();
index.empty();
ans.empty();
}
void printAdjacencyWords(){
essay.empty();
index.empty();
ans.empty();
int* pos=new int[wordNum];
memset(pos,0,4*wordNum);
bool find=true;
int prepos;
int count=1;
while(find){
find=false;
int p=0x7fffffff;
int min;
for(int i=0;i<wordNum;++i)
if(pos[i]<words[i].wordFreq&&p>words[i].pos[pos[i]]){
find=true;
p=words[i].pos[pos[i]];
min=i;
}
if(find){
if(count==1){
prepos=p;
index.push_back(p);
essay.push_back(min);
}
else{
if(p==prepos+1){
index.push_back(p);
essay.push_back(min);
}
else{
index.push_back(-1);
index.push_back(p);
essay.push_back(-1);
essay.push_back(min);
}
prepos=p;
}
++count;
pos[min]=pos[min]+1;

}
}
/*
{
for(int i=0;i<essay.size();++i)
if(essay[i]!=-1)
cout<<words[essay[i]].word;
else cout<<" ";
cout<<endl;
}*/

int l=essay.size();
int bpos=0,epos=0;
for(int i=0;i<l;++i){
if(essay[i]==-1){
if((epos-bpos)>=1)
cal(bpos,epos);
bpos=i+1,epos=i+1;
continue;
}
else{
epos=i;
}
}
if(epos-bpos>=1)
cal(bpos,epos);

string t="";
count=1;
for(multimap<string,string>::iterator p=ans.begin();p!=ans.end();++p){
if(t!=p->first){
if(count!=1)
cout<<")"<<endl;
++count;
t=p->first;
cout<<t<<"("<<p->second;
}
else{
cout<<";"<<p->second;
}
}
cout<<")"<<endl;

}
private:
void cal(int bpos,int epos){
for(int from=bpos;from<epos;++from){
string w=words[essay[from]].word;
string pos=numToString(index[from]);
for(int end=from+1;end<=epos;++end){
w+=words[essay[end]].word;
pos+=",";
pos+=numToString(index[end]);
ans.insert(make_pair(w,pos));
}
}
}
string numToString(int n){
string s="";
do{
char t=n%10+'0';
s=t+s;
n/=10;
}while(n);
return s;
}
int wordNum;
WORD* words;
vector<int> essay;
vector<int> index;
multimap<string,string> ans;
};
int main(){
int wordsNum;
cin>>wordsNum;
WORD *words=new WORD[wordsNum];
for(int i=0;i<wordsNum;++i){
cin>>words[i].word;
cin>>words[i].wordFreq;
for(int j=0;j<words[i].wordFreq;++j)
cin>>words[i].pos[j];
}
Essay essay(wordsNum,words);
essay.printAdjacencyWords();

return 0;
}
结贴给分吧

C/C++ code

/*
前提假设所有的页码已经是递增序列，如果没有此限定，自己排序即可

  输入 
  3                                    //代表3个单词
  我
  5                                    //代表5个pos
  0 11 20 90 120
  爱
  5
  1 21 121 200 300
  你
  4
  2 22 80 30

  主要思路按照索引依次填入相应位置，相邻的话紧挨着，不相邻中间插入隔断符号以节省空间
  完成后顺序扫描即可
*/
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
using namespace std;

typedef struct WORD{
    string word;
    int pos[100];
    int wordFreq;
}WORD;

class Essay{
public:
    Essay(int n,WORD* w):wordNum(n),words(w){
        essay.empty();
        index.empty();
        ans.empty();
    }
    void printAdjacencyWords(){
        essay.empty();
        index.empty();
        ans.empty();
        int* pos=new int[wordNum];
        memset(pos,0,4*wordNum);
        bool find=true;
        int prepos;
        int count=1;
        while(find){
            find=false;
            int p=0x7fffffff;
            int min;
            for(int i=0;i<wordNum;++i)
                if(pos[i]<words[i].wordFreq&&p>words[i].pos[pos[i]]){
                    find=true;
                    p=words[i].pos[pos[i]];
                    min=i;
                }
            if(find){
                if(count==1){
                    prepos=p;
                    index.push_back(p);
                    essay.push_back(min);
                }
                else{
                    if(p==prepos+1){
                        index.push_back(p);
                        essay.push_back(min);
                    }
                    else{
                        index.push_back(-1);
                        index.push_back(p);
                        essay.push_back(-1);
                        essay.push_back(min);
                    }
                    prepos=p;
                }
                ++count;
                pos[min]=pos[min]+1;
                    
            }
        }
        /*
        {
            for(int i=0;i<essay.size();++i)
                if(essay[i]!=-1)
                    cout<<words[essay[i]].word;
                else cout<<" ";
            cout<<endl;
        }*/
        
        int l=essay.size();
        int bpos=0,epos=0;
        for(int i=0;i<l;++i){
            if(essay[i]==-1){
                if((epos-bpos)>=1)
                    cal(bpos,epos);
                bpos=i+1,epos=i+1;
                continue;
            }
            else{
                epos=i;
            }
        }
        if(epos-bpos>=1)
            cal(bpos,epos);

        string t="";
        count=1;
        for(multimap<string,string>::iterator p=ans.begin();p!=ans.end();++p){
            if(t!=p->first){
                if(count!=1)
                    cout<<")"<<endl;
                ++count;
                t=p->first;
                cout<<t<<"("<<p->second;
            }
            else{
                cout<<";"<<p->second;
            }
        }
        cout<<")"<<endl;

    }
private:
    void cal(int bpos,int epos){
        for(int from=bpos;from<epos;++from){
            string w=words[essay[from]].word;
            string pos=numToString(index[from]);
            for(int end=from+1;end<=epos;++end){
                w+=words[essay[end]].word;
                pos+=",";
                pos+=numToString(index[end]);
                ans.insert(make_pair(w,pos));
            }
        }
    }
    string numToString(int n){
        string s="";
        do{
            char t=n%10+'0';
            s=t+s;
            n/=10;
        }while(n);
        return s;
    }
    int wordNum;
    WORD* words;
    vector<int> essay;
    vector<int> index;
    multimap<string,string> ans;
};
int main(){
    int wordsNum;
    cin>>wordsNum;
    WORD *words=new WORD[wordsNum];
    for(int i=0;i<wordsNum;++i){
        cin>>words[i].word;
        cin>>words[i].wordFreq;
        for(int j=0;j<words[i].wordFreq;++j)
            cin>>words[i].pos[j];
    }
    Essay essay(wordsNum,words);
    essay.printAdjacencyWords();

    return 0;
}

结贴给分吧