字符串匹配问题

现在有一字符串Q，需要让Q中不能出现P字符串，如何在o(lenQ+lenP)下办到

比如Q=absabsdde
P=absd

那么最后结果为e

11 个解决方案

#1

是判断Q中是否存在P么? 为什么结果是e?

#2

从效率要求上看很象kmp

#3

好象按字符一个个比过来也是符合要求的吧.

#4

将Q进行链表结构存放
扫描整个Q链表， 查找P的第一个字符在Q中出现的位置，保存在一个指针数组PA中
然后逆向检查PA，对Q中的节点进行检查

#5

类似于哈希,
根据p建立长度为256的表,分别表示ASCII(i)是否在p中(O(lenP))
然后对Q中的每个字母,查找表中的状态,如果是在P中,则删除.(O(lenQ))

#6

没有其它条件约束的话,不存在这种通用算法

#7

楼主可以考虑下KMP算法

#8

如果P的第一个字符在P后面的任意位置不重复("abcadef"则不符合规则),可以做到o(2*lenQ)

#9

就直接把P的每一个字符放在一个数组中进行索引，也就是hash ，然后遍历Q就行了，每一次看看在不在P中

#10

编译原理中可能有你想要的答案。

#11

引用 5 楼 fire_woods 的回复:

类似于哈希, 
根据p建立长度为256的表,分别表示ASCII(i)是否在p中(O(lenP)) 
然后对Q中的每个字母,查找表中的状态,如果是在P中,则删除.(O(lenQ))

恩 空间换时间可以做到

#include<iostream>
#include<cstring>
using namespace std;

int a[128];

int main()
{
  char s[]="I love you";
  char d[]="ou";
  int n1=strlen(d);
  for(int i=0;i<n1;++i)
    a[d[i]]=1;
  int n2=strlen(s);
  char* p=new char[n2+1];
  char* c=p;
  int j=0;
  for(int i=0;i<n2;++i)
  {
   if(a[s[i]]==0) c[j++]=s[i];
  } 
  c[j]='\0';
  cout<<p<<endl;
  delete []p;
  system("pause");
  return 0;
}