#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int index(const char * str1, const char * str2, size_t pos = 0);
bool match(const char* T, const char* P, int& start, int& end);
int main(int argc, char *argv[])
{
char str[] = "we are the are the world!";
char *pch;
/*
pch = strstr(str,"are");
cout<<str<<endl<<pch<<endl;
int i = index(str," ");
cout<<str<<endl<<&str[i]<<endl;*/
char pattern[] = "***********************************************t???";
int i, j;
if(match(str, pattern, i, j))
for(int k=i; k<=j; k++)
cout<<str[k];
cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
int index(const char * str1, const char * str2, size_t pos)
{
size_t i = pos;
size_t j = 0;
while(i < strlen(str1) && j < strlen(str2))
{
if(str1[i] == str2[j]) // matched then continue
{
++i;
++j;
}
else // unmatched then backtrace
{
i = i - j + 1;
j = 0;
}
}
if(j >= strlen(str2)) // matched and return the index
return i-strlen(str2);
else
return -1; // not found
}
/*
*decrip:match the string('*' and '?' not included) with pattern including *(se
* veral),?(only one)
*input:
* T -- text
* P -- Pattern
*return:
* true for exit ,false for not
* start,end -- the index of the pattern found in the text
*/
bool match(const char* T, const char* P, int& start, int& end)
{
size_t i = 0;
size_t j =0;
size_t n = strlen(T);
size_t m = strlen(P);
bool bStart = true;
while(i < n && j < m)
{
if(P[j] == '*') // wildcard ,then find the first position matched with next character
{
++j;
while('*' == P[j]) // "***..*" <=> "*"
++j;
while(T[i] != P[j])
++i;
if(i >= n) // finished, no matter matched or not
break;
}
if(T[i] == P[j] || '?' == P[j])
{
if(bStart) // new loop start
{
start = i;
bStart = false;
}
++i;
++j;
if(j == m) // match finish
end = i-1;
}
else // unmatched ,then backtrace(start a new loop)
{
static size_t ipp = 0;
++ipp;
i = ipp;
j = 0;
bStart = true;
}
}
if(j >= m) // succeeded to find the pattern
{
if( '*' == P[0]) // postfix
start = 0;
if( '*' == P[m-1]) // prefix
end = n-1;
return true;
}
else
return false;
}
评论3