C++字符串匹配程序

fenghua26

算法要求就是：先子串的第一个字符与主串第一个字符进行匹配，然后子串最后一个与主串的第一个后+子串长度后的那个字符进行匹配，再子串第二个字符与主串第二个匹配，依次如此。。。如果匹配不成功再子串第一个与主串第二个匹配，再按原来的方式进行匹配
.比如：
主串： abdfefds
子串：dfe
先子串d与主串a进行匹配,匹配不成功;
则子串d与主串b进行匹配还是不匹配;
再子串d与主串d进行匹配能匹配;
然后子串最后一个字符e与主串e进行匹配匹配成功;
然后子串f与主串f进行匹配能匹配成功，
匹配成功！能匹配 返回主串中能匹配成功的首个字符在主串中的位置!

菜鸟跪求各位高手!请赐教!谢谢

liuyuning

看不明白...

boxer2005

楼主说的是不是一般意义的“字符串匹配”啊？

master20404

LZ这样跟直接按顺序匹配有什么区别？
按你的这种顺序匹配，如果待匹配的字符串是8个，你要怎样的匹配顺序阿？

zjwzjw

朴素(Naive)字符串匹配算法, 作为最原始的字符串匹配算法，它的时间复杂度是O((n-m+1)m)

#include "stdio.h"

//计算字符串的长度
int Length(char *s)
{
int count=0;
while(*s++!='\0')
  count++;

return count;
}

//字符串匹配
void NaiveStringMatching(char *t,char *p)
{
int n=Length(t);
int m=Length(p);
if(n<m)
{
  printf("Error:The P is longer than T!\n");
  return;
}

bool find=true;

printf("The string T is %s\n",t);
printf("The string P is %s\n",p);
for(int s=0;s<=n-m;s++)
{
  find=true;
  for(int i=0;i<m;i++)
  {
   if(t[s+i]!=p[i])
   {
    find=false;
    break;
   }
  }
  if(find)   
   printf("Pattern occurs with shift:%d\n",s+1);
}
}

int main()
{
char t[]="abcdebcg";
char p[]="bcdebcg";

NaiveStringMatching(t,p);
return 0;
}

fenghua26

楼主说的是不是一般意义的“字符串匹配”啊？

-----------一般的的字符串匹配是先子串第一个字符与主串第一个字符进行匹配,然后第二个...再到最后一个,
而我说的这种算法是一种改进后的匹配算法:先匹配第一次字符串再进行最后一个字符匹配,
比如:主串adfet 子串:adft
先子串中的a与主串中的a匹配,马上进行子串的t与主串的e进行匹配,不匹配跳出,进入子串第1个字符与主串第2个字符的匹配...
显然要比普通的匹配要好些

fenghua26

高手快来help下啊

master20404

LZ真是有趣，哪有效率的提高阿，匹配的字符次数都是一样的。
主串是abcde,子串是atcd的话，直接一个个比较在第二次就能发现不同，你这种方法要在第几次发现呢？
匹配算法最快的应该是KMP算法（有点忘了，不知道是不是叫这个），O(n)的效率。

fenghua26

#include<iostream.h>
#include<string.h>

//#define MAXSTRLEN 255
//typedef  char string[MAXSTRLEN+1];
//using namespace std;

int find(char *str1,char *str2)
//S为主串，T为子串
{
  int index=1;
  char *p,*m,*q,*n;
  char *Sstart,*Send,*Tstart,*Tend;
  Sstart=str1;
  Tstart=str2;
  Send=Sstart+strlen(str2)-1;
  Tend=Tstart+strlen(str2)-1;
  p=Sstart;
  m=Tstart;
  q=p+strlen(str2)-1;
  n=q+strlen(str2)-1;
  if(strlen(str1)<strlen(str2))
         {
      
       cout<<"子串比主串长不能进行匹配!"<<endl;
           return -1;
  }//if
  else
  
  {
  while(q<=str1+strlen(str1))
        {
          if(*p==*m&&*q==*n)
          {
                  p++;q--;
                  m++;n--;
                  if(p=q)
                  { cout<<"匹配成功"<<endl<<"从主串第"<<index<<"个字符开始匹配"<<endl;break;}

                  
          }
          else
          {   index++;
                  Sstart++;Send++;
                 
                  
                  if(Send>str1+strlen(str1)-1)
                  { cout<<"匹配不成功!";
                    break;
                  }
                  else
                  {
            p=Sstart;q=Send;
            m=Tstart;
                    n=Tend;
                  }
                         // cout<<"匹配成功!"<<endl<<"从主串第"<<index<<"个字符开始匹配!"<<endl;

          }       
          
  
        }//while
   
   
  }//else
        return 1;
}
  
void main()
{
          char   str1[255],str2[255];
          cout<<"请输入主串:";
          cin>>str1;
          cout<<endl;
          cout<<"请输入子串:";
          cin>>str2;
          cout<<endl;
         find(str1,str2);
}
       
  // cout<<find(str1,str2)<<endl;  



还是只能靠自己啊

master20404

LZ用了那么多strlen又无序的逐字节比较，效率比你所BS的直接逐字节比较还低-_-b