C ++ string matching program

fenghua26

The algorithm requirements are: first the first character of the substring matches the first character of the main string, then the last of the substring matches the first character of the main string + the character after the length of the substring, and then the first character of the substring The two characters match the second in the main string, and so on. . . If the match is unsuccessful, then the first substring matches the second main string, and then the original match is performed.
.such as:
Main string: abdfefds
Substring: dfe
The first substring d matches the main string a, and the match is unsuccessful;
Does the substring d match the main string b or not?
The substring d can be matched with the main string d;
Then the last character e of the substring matches the main string e.
Then the matching between the substring f and the main string f can be successful.
Match successful! Matchable Returns the position of the first character in the main string that can be successfully matched in the main string!

Novice begged masters! Please enlighten me! Thank you

liuyuning

Do not understand...

boxer2005

Is the landlord saying "string matching" in the general sense?

master20404

What is the difference between LZ and direct matching?
Match in this order. If there are 8 strings to be matched, what is the matching order?

zjwzjw

Naive string matching algorithm, as the most primitive string matching algorithm, its time complexity is O ((n-m + 1) m)

#include "stdio.h"

// Calculate the length of the string
int Length (char * s)
{
 int count = 0;
 while (* s ++! = '\0')
  count ++;

 return count;
}

// string match
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

Is the landlord saying "string matching" in the general sense?

----------- General string matching is to match the first character of the first substring with the first character of the main string, then the second ... to the last,
The algorithm I said is an improved matching algorithm: the first string is matched before the last character is matched.
For example: main string adfet substring: adft
First, the a in the substring matches the a in the main string, and the t of the substring is matched with the e of the main string immediately. If there is no match, the first character of the substring and the second character of the main string are matched. .
Obviously better than ordinary matches

fenghua26

Masters help soon

master20404

LZ is really interesting. How can the efficiency be improved? The number of matching characters is the same.
If the main string is abcde, and the substring is atcd, you can find the difference in the second time by directly comparing one by one. How many times do you find this method?
The fastest matching algorithm should be the KMP algorithm (a bit forgotten, I don't know if it's called this), O (n) efficiency.

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 is the main string, T is the substring
{
  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<<"The substring is longer than the main string and cannot be matched!"<<endl;
return -1;
  }//if
  else
  
  {
  while(q<=str1+strlen(str1))
{
if(*p==*m&&*q==*n)
{
p++;q--;
m++;n--;
if(p=q)
{cout<<"matched successfully"<<endl<<"match from the first "<<index<<" characters of the main string"<<endl;break;}

The
}
else
{index++;
Sstart++;Send++;
The
The
if(Send>str1+strlen(str1)-1)
{cout<<"The match was not successful!";
break;
}
else
{
            p=Sstart;q=Send;
            m=Tstart;
n=Tend;
}
// cout<<"matched successfully!"<<endl<<"match from the "<<index<<" character of the main string!"<<endl;

}
The
  
}//while
   
   
  }//else
return 1;
}
  
void main()
{
char str1[255],str2[255];
cout<<"Please enter the main string:";
cin>>str1;
cout<<endl;
cout<<"Please enter substring:";
cin>>str2;
cout<<endl;
find(str1,str2);
}
The
  // cout<<find(str1,str2)<<endl;



I still have to rely on myself

master20404

LZ uses so many strlen and out-of-order byte-by-byte comparison, the efficiency is lower than the direct byte-by-byte comparison of your BS-_-b