寒假专题训练--字符串

字符串

地址

B - Oulipo

[HDU - 168]

• 题意
  已知两个由大写字母构成的字符串W和T。求在字符串T中，字符串W出现了几次（可重叠）。
• 思路
  字符串W与T的长度都较大，显然O(mn)的暴力处理方式会超时。考虑KMP算法，时间复杂度为O（m+n)。
• 代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <queue>
using namespace std;
int t,ans,Next[10005];
char w[10005],te[1000005];
void getNext(){
  int len=strlen(w),j=0;
  Next[0]=Next[1]=0;
  for (int i = 1; i < len; ++i)
  {
    while(j>0&&w[i]!=w[j]){
      j=Next[j];
    }
    if (w[i]==w[j])
    {
      j++;
    }
    Next[i+1]=j;
  }
}
void search(){
  int j=0,lent=strlen(te),lenw=strlen(w);
  for (int i = 0; i < lent; ++i)
  {
    while(j>0&&te[i]!=w[j]){
      j=Next[j];
    }
    if (te[i]==w[j])
    {
      j++;
    }
    if (j==lenw)
    {
      ans++;
      j=Next[j];
    }
  }
}
int main(){
  scanf("%d",&t);
  while(t--){
    ans=0;
    scanf("%s%s",w,te);
    getNext();
    search();
    printf("%d\n",ans );
  }
  return 0;
}

D - 统计难题

[HDU - 1251]

• 题意
  给出一个含有多个单词的单词表。对于一个给定的字符串，求出有多少个以其为前缀的单词。
• 思路
  根据单词表建立字典树。对于给定的字符串，在字典树中一层层往下找。
• 代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define M 26
int num;
char t[15],w;
struct tree{
  tree *next[M];
  int v;
}*root;
void create(char *str,int len){
  //int len=strlen(str);
  tree *p=root,*q=NULL;
  for (int i = 0; i < len; ++i)
  {
    int id=str[i]-'a';
    if (p->next[id]==NULL)
    {
      q=(tree *)malloc(sizeof(tree));
      for (int j = 0; j < M; ++j)
      {
        q->next[j]=NULL;
      }
      q->v=1;
      p->next[id]=q;
      p=p->next[id];
    }else{
      p=p->next[id];
      p->v++;
    }
  }
  //p-v=-1;
}
int search(char *str,int len){
  //int len=strlen(str);
  tree *p=root;
  for (int i = 0; i < len; ++i)
  {
    int id=str[i]-'a';
    p=p->next[id];
    if (p==NULL)
    {
      return 0;
    }
  }
  return p->v;
}
int main(){
  num=0;
  root=(tree *)malloc(sizeof(tree));
  for (int i = 0; i < M; ++i)
  {
    root->next[i]=NULL;
  }
  while(1){
    w=getchar();
    if (w=='\n')
    {
      create(t,num);
      num=0;
      w=getchar();
      if (w=='\n')
      {
        break;
      }
    }
    t[num++]=w;
  }
  num=0;
  while(~scanf("%c",&w)){
    if (w=='\n')
    {
      printf("%d\n",search(t,num));
      num=0;
      continue;
    }
    t[num++]=w;
  }
  return 0;
}