输入是一个TERM数组，输出其中任意一个集合ID

现有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个集合包含1~M个TERM（M为0~100的量级），希望设计一个程序能够持续对外服务，输入是一个TERM数组，输出其中任意一个集合ID（如果该TERM数组包含该集合的所有TERM），如果找不到输出-1。要求：

1，  时间复杂度最优，能够在短时间内对大量输入逐个输出

2，  实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库。

3，  给出时间复杂度和空间复杂度。

TERM组合集合的文件格式举例：

TERM_1 空格 TERM_2

TERM_1 空格 TERM_3

TERM_1 空格 TERM_3  TERM_4

输入的为TERM数组（说明：TERM为一个词，可能是中文，固定字符串表示）

 

eg:

  a_1 aa_2
  b_11 bb_22
  c_111 cc_222 ccc_444

 

input：

  c cc ccc

ouput:

  111

 

input：

  aa cc ccc

ouput:

  -1

 

大致思路我这里把输入的数组做hash,以方便O(1)查找。

集合可以理解为二维链表

set是集合链表, term是集合内的term链表

 

也不知道自己这么理解对不对,一家之言!大家有什么好思路不妨共享

 

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_TERM 10
#define MAX_LEN 100

#define HASH_N 13

typedef struct term
{
  char str[MAX_TERM];
  int id;
  struct term* next;
}TERM;

typedef struct set
{
  TERM* term;
  struct set* next;
}SET;

typedef struct hash
{
  char* key;
  struct hash* next;
}HASH;

HASH* H[HASH_N];
 
void init_term(TERM** T)
{
  *T = (TERM*)malloc(sizeof(TERM));
  memset((*T)->str, 0, MAX_TERM);
  (*T)->id = 0;
  (*T)->next = NULL;
}

void init_set(SET** S)
{
  *S = (SET*)malloc(sizeof(SET));
  (*S)->term = NULL;
  (*S)->next = NULL;
}

void init_hash()
{
  int i;
  for(i=0;i<HASH_N;i++)
   {
     H[i] = (HASH*)malloc(sizeof(HASH));
     H[i]->key = NULL;
     H[i]->next = NULL;
   }
}

int get_term_id(char* term_id, TERM* T)
{
  char* tmp = term_id;
  TERM* p = (TERM*)malloc(sizeof(TERM));
  int i = 0;
  
  while(tmp[i]!='\0')
   {
     i++;
     if(tmp[i] == '_')
      {
       tmp[i] = '\0';
       sprintf(p->str, "%s", tmp);
       p->id = atoi(tmp+i+1);
      }
   }
   p->next = T->next;
   T->next = p;
   return 0;
}
        
int process_line(char* line,SET* S)
{
  int i = 0;
  char* line_tmp = line;
  TERM* T = NULL;
  SET* p = (SET*)malloc(sizeof(SET));
  init_term(&T);
  char term[MAX_TERM];
     
  while(line_tmp[i] != '\0')
   {
     i++;
     if(line_tmp[i] == ' ')
      {
        snprintf(term, i, "%s", line_tmp);
        term[i] = '\0';
        get_term_id(line_tmp,T);
        i++;
        line_tmp += i;
        i = 0;
      }
     if(line_tmp[i] == '\0')
     {
      //line_tmp[i-1]='\0';

      get_term_id(line_tmp,T);
      break;
     }
   }
  p->term = T;
  p->next = S->next;
  S->next = p;
  return 0;
}

void print_set(SET* S)
{
  SET* p = S->next;
  while(p!=NULL)
   {
     TERM* q = p->term->next;
     while(q!=NULL)
      {
        printf("term:%s\tid:%d\n", q->str, q->id);
        q = q->next;
      }
     p = p->next;
   }
}

void print_hash()
{
  int i;
  
  for(i=0;i<HASH_N;i++)
   {
     HASH* p = H[i]->next;
     while(p!=NULL)
      {
        printf("hash str is %s\n",p->key);
        p = p->next;
      }
   }
}
  
unsigned int BKDRHash(char* str)
{
  unsigned int seed = 131;
  unsigned int hash = 0;
  while(*str)
   {
     hash = hash*seed + *str++;
   }
  return hash&0x7FFFFFFF;
}

void add_hash(char* term)
{
  //printf("term is %s\n", term);

  unsigned int hash_num = BKDRHash(term);
  
  HASH* p = (HASH*)malloc(sizeof(HASH));
  p->key = term;
  
  hash_num %= HASH_N;
  
  p->next = H[hash_num]->next;
  H[hash_num]->next = p;
}
      
void process_input(char* line)
{
   char* tmp_line = line;
   int i = 0;
   
   while(tmp_line[i]!='\0')
    {
      i++;
      if(tmp_line[i]==' ')
       {
         char* term = (char*)malloc(MAX_TERM);
         snprintf(term, i, "%s", tmp_line);
         term[i] = '\0';
         add_hash(term);
         i++;
         tmp_line += i;
         i = 0;
        }
      if(tmp_line[i]=='\0')
       {
         tmp_line[i-1]='\0';
         add_hash(tmp_line);
         break;
       }
    }
}

int exist(char* str)
{
  unsigned int hash_num = BKDRHash(str);
  
  hash_num %= HASH_N;
  
  HASH* p = H[hash_num]->next;
  
  while(p!=NULL)
  {
    if(strcmp(str,p->key) == 0)
      return 1;
  }
  return 0;
}
int judge_terms(SET* S)
{
  SET* p = S->next;
  while(p!=NULL)
   {
     TERM* q = p->term->next;
     while(q!=NULL)
      {
        if(exist(q->str))
         {
          if(q->next == NULL)
            return q->id;
           
          q = q->next;
         }
        else
          break;
      }
     p = p->next;
   }
  return -1;
}
    
int main(int argc, char *argv[])
{
  int ret = 0;
  SET* S = NULL;
  init_set(&S);
  char line[MAX_LEN];
  
  init_hash();
    
  FILE* fp = fopen("term.txt","r");
  while(fgets(line, MAX_LEN, fp))
   {
     process_line( line, S);
   }
  print_set(S);
  
  printf("Please input the terms you want:\n");
  fgets(line, MAX_LEN, stdin);
  printf("you input is %s\n",line);
  
  process_input(line);
  
  print_hash();
  
  ret = judge_terms(S);
  printf("ret is %d\n",ret);
  fclose(fp);
  system("PAUSE");    
  return 0;
}