Это вопрос в моем бумажном тесте сегодня, подпись функции
int is_match(char* pattern,char* string)
Шаблон ограничен только символами ASCII и квантификацией * и ?, поэтому он относительно прост. is_match должен возвращать 1, если соответствует, в противном случае 0.
Как это сделать?
См. Этот вопрос для решения, которое вы не можете отправить. См. этот документ для описания того, как реализовать более читаемый.
Здесь приведена рекурсивная расширяемая реализация. Протестировано для первого порядка сложности шаблонов.
#include <string.h>
#include <string>
#include <vector>
#include <iostream>
struct Match {
Match():_next(0) {}
virtual bool match(const char * pattern, const char * input) const {
return !std::strcmp(pattern, input);
}
bool next(const char * pattern, const char * input) const {
if (!_next) return false;
return _next->match(pattern, input);
}
const Match * _next;
};
class MatchSet: public Match {
typedef std::vector<Match *> Set;
Set toTry;
public:
virtual bool match(const char * pattern, const char * input) const {
for (Set::const_iterator i = toTry.begin(); i !=toTry.end(); ++i) {
if ((*i)->match(pattern, input)) return true;
}
return false;
}
void add(Match * m) {
toTry.push_back(m);
m->_next = this;
}
~MatchSet() {
for (Set::const_iterator i = toTry.begin(); i !=toTry.end(); ++i)
if ((*i)->_next==this) (*i)->_next = 0;
}
};
struct MatchQuestion: public Match {
virtual bool match(const char * pattern, const char * input) const {
if (pattern[0] != '?')
return false;
if (next(pattern+1, input))
return true;
if (next(pattern+1, input+1))
return true;
return false;
}
};
struct MatchEmpty: public Match {
virtual bool match(const char * pattern, const char * input) const {
if (pattern[0]==0 && input[0]==0)
return true;
return false;
}
};
struct MatchAsterisk: public Match {
virtual bool match(const char * pattern, const char * input) const {
if (pattern[0] != '*')
return false;
if (pattern[1] == 0) {
return true;
}
for (int i = 0; input[i] != 0; ++i) {
if (next(pattern+1, input+i))
return true;
}
return false;
}
};
struct MatchSymbol: public Match {
virtual bool match(const char * pattern, const char * input) const {
// TODO: consider cycle here to prevent unnecessary recursion
// Cycle should detect special characters and call next on them
// Current implementation abstracts from that
if (pattern[0] != input[0])
return false;
return next(pattern+1, input+1);
}
};
class DefaultMatch: public MatchSet {
MatchEmpty empty;
MatchQuestion question;
MatchAsterisk asterisk;
MatchSymbol symbol;
public:
DefaultMatch() {
add(&empty);
add(&question);
add(&asterisk);
add(&symbol);
}
void test(const char * p, const char * input) const {
testOneWay(p, input);
if (!std::strcmp(p, input)) return;
testOneWay(input, p);
}
bool testOneWay(const char * p, const char * input) const {
const char * eqStr = " == ";
bool rv = match(p, input);
if (!rv) eqStr = " != ";
std::cout << p << eqStr << input << std::endl;
return rv;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
typedef vector<string> Strings;
Strings patterns;
patterns.push_back("*");
patterns.push_back("*hw");
patterns.push_back("h*w");
patterns.push_back("hw*");
patterns.push_back("?");
patterns.push_back("?ab");
patterns.push_back("a?b");
patterns.push_back("ab?");
patterns.push_back("c");
patterns.push_back("cab");
patterns.push_back("acb");
patterns.push_back("abc");
patterns.push_back("*this homework?");
patterns.push_back("Is this homework?");
patterns.push_back("This is homework!");
patterns.push_back("How is this homework?");
patterns.push_back("hw");
patterns.push_back("homework");
patterns.push_back("howork");
DefaultMatch d;
for (unsigned i = 0; i < patterns.size(); ++i)
for (unsigned j =i; j < patterns.size(); ++j)
d.test(patterns[i].c_str(), patterns[j].c_str());
return 0;
}
Если что-то неясно, спросите.
Брайан Керниган представил короткую статью о Регулярный эквивалент выражения, что Rob Pike написал как демонстрационную программу для книги, над которой они работали. В статье очень приятно читать, объясняя немного о коде и регулярных выражениях вообще.
Я сыграл с этим кодом, внеся несколько изменений в эксперимент с некоторыми расширениями, например, чтобы вернуть туда, где в строке соответствует шаблон, чтобы подстрока, соответствующая шаблону, могла быть скопирована из исходного текста.
Из статьи:
Я предложил Робу, что нам нужно найти самый маленький который будет иллюстрировать основные идеи, пока признавая полезный и нетривиальный класс шаблонов. В идеале код будет помещаться на одной странице.
Роб скрылся в своем кабинете, и, по крайней мере, когда я это помню, снова появляется не более чем через час или два с 30 линиями C код, который впоследствии появился в главе 9 TPOP. Этот код реализует элемент регулярного выражения, который обрабатывает эти конструкции:c matches any literal character c . matches any single character ^ matches the beginning of the input string $ matches the end of the input string * matches zero or more occurrences of the previous characterЭто довольно полезный класс; в моем собственном опыте использования регулярных выражений на повседневной основе, он легко составляет 95 процентов всех случаев. Во многих ситуациях решение правильной проблемы - это большой шаг на пути к красивой программе. Роб заслуживает большого кредита для выбора так разумно, из широкого набора опций, очень мало но важный, четко определенный и расширяемый набор функций.
Сама реализация Rob - превосходный пример красивого кода: компактный, элегантный, эффективный и полезный. Это один из лучших примеров рекурсии, которую я когда-либо видел, и показывает силу C указатели. Хотя в то время нас больше всего интересовало важная роль хорошей нотации в упрощении программы использовать и, возможно, проще писать, код регулярного выражения также является отличным способом иллюстрации алгоритмов, данных структур, тестирования, повышения производительности и других важных темы.
Фактический исходный код C из статьи очень приятный.
/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
if (regexp[0] == '^')
return matchhere(regexp+1, text);
do { /* must look even if string is empty */
if (matchhere(regexp, text))
return 1;
} while (*text++ != '\0');
return 0;
}
/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
if (regexp[0] == '\0')
return 1;
if (regexp[1] == '*')
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == '$' && regexp[1] == '\0')
return *text == '\0';
if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
return matchhere(regexp+1, text+1);
return 0;
}
/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
do { /* a * matches zero or more instances */
if (matchhere(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
Чит. Используйте #include <boost/regex/regex.hpp>.
Не тестировал это, на самом деле его кодировал или отлаживал, но это может привести к запуску...
for each character in the pattern
if pattern character after the current one is *
// enter * state
while current character from target == current pattern char, and not at end
get next character from target
skip a char from the pattern
else if pattern character after the current one is ?
// enter ? state
if current character from target == current pattern char
get next char from target
skip a char from the pattern
else
// enter character state
if current character from target == current pattern character
get next character from target
else
return false
return true
попытайтесь составить список интересных тестовых случаев:
is_match ("dummy", "dummy") должен return true;
is_match ( "dumm? y", "dummy") должен return true;
is_match ( "дум? У", "dummy") должен возвращать false;
is_match ( "dum * y", "dummy") должен return true;
и т.д.
то посмотрите, как сделать более простой тестовый проход, затем следующий...
Для решения этой проблемы не требуется полная мощность регулярных выражений и конечных автоматов. В качестве альтернативы существует относительно простое решение динамического программирования.
Пусть match (i, j) равно 1, если можно сопоставить строку подстроки [i..n-1] с шаблоном поднабора [j, m - 1], где n и m - это длины строки и рисунка соответственно. В противном случае пусть match (i, j) будет 0.
Основными случаями являются:
match (n, m) = 1, вы можете сопоставить пустую строку с пустым шаблоном;
match (i, m) = 0, вы не можете сопоставить непустую строку с пустым шаблоном;
Переход делится на 3 случая в зависимости от того, начинается ли текущая подзапись с символом, за которым следует символ '*', или символ, за которым следует '?' или просто начинается с символа без специального символа после него.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int is_match(char* pattern, char* string)
{
int n = strlen(string);
int m = strlen(pattern);
int i, j;
int **match;
match = (int **) malloc((n + 1) * sizeof(int *));
for(i = 0; i <= n; i++) {
match[i] = (int *) malloc((m + 1) * sizeof(int));
}
for(i = n; i >= 0; i--) {
for(j = m; j >= 0; j--) {
if(i == n && j == m) {
match[i][j] = 1;
}
else if(i < n && j == m) {
match[i][j] = 0;
}
else {
match[i][j] = 0;
if(pattern[j + 1] == '*') {
if(match[i][j + 2]) match[i][j] = 1;
if(i < n && pattern[j] == string[i] && match[i + 1][j]) match[i][j] = 1;
}
else if(pattern[j + 1] == '?') {
if(match[i][j + 2]) match[i][j] = 1;
if(i < n && pattern[j] == string[i] && match[i + 1][j + 2]) match[i][j] = 1;
}
else if(i < n && pattern[j] == string[i] && match[i + 1][j + 1]) {
match[i][j] = 1;
}
}
}
}
int result = match[0][0];
for(i = 0; i <= n; i++) {
free(match[i]);
}
free(match);
return result;
}
int main(void)
{
printf("is_match(dummy, dummy) = %d\n", is_match("dummy","dummy"));
printf("is_match(dumm?y, dummy) = %d\n", is_match("dumm?y","dummy"));
printf("is_match(dum?y, dummy) = %d\n", is_match("dum?y","dummy"));
printf("is_match(dum*y, dummy) = %d\n", is_match("dum*y","dummy"));
system("pause");
return 0;
}
Временной сложностью этого подхода является O (n * m). Сложность памяти также O (n * m), но с простой модификацией можно свести к O (m).
Простая рекурсивная реализация. Это медленно, но легко понять:
int is_match(char *pattern, char *string)
{
if (!pattern[0]) {
return !string[0];
} else if (pattern[1] == '?') {
return (pattern[0] == string[0] && is_match(pattern+2, string+1))
|| is_match(pattern+2, string);
} else if (pattern[1] == '*') {
size_t i;
for (i=0; string[i] == pattern[0]; i++)
if (is_match(pattern+2, string+i)) return 1;
return 0;
} else {
return pattern[0] == string[0] && is_match(pattern+1, string+1);
}
}
Надеюсь, у меня все получилось.
Программа C для поиска индекса, откуда начнется подстрока в основной строке. введите код здесь
#include<stdio.h>
int mystrstr (const char *,const char *);
int mystrcmp(char *,char *);
int main()
{
char *s1,*s2;//enter the strings, s1 is main string and s2 is substring.
printf("Index is %d\n",mystrstr(s1,s2));
//print the index of the string if string is found
}
//search for the sub-string in the main string
int mystrstr (const char *ps1,const char *ps2)
{
int i=0,j=0,c=0,l,m;char *x,*y;
x=ps1;
y=ps2;
while(*ps1++)i++;
while(*ps2++)j++;
ps1=x;
ps2=y;
char z[j];
for(l=0;l<i-j;l++)
{
for(m=l;m<j+l;m++)
//store the sub-string of similar size from main string
z[c++]=ps1[m];
z[c]='\0'
c=0;
if(mystrcmp(z,ps2)==0)
break;
}
return l;
}
int mystrcmp(char *ps3,char *ps4) //compare two strings
{
int i=0;char *x,*y;
x=ps3;y=ps4;
while((*ps3!=0)&&(*ps3++==*ps4++))i++;
ps3=x;ps4=y;
if(ps3[i]==ps4[i])
return 0;
if(ps3[i]>ps4[i])
return +1;
else
return -1;
}
enter code here
#include<stdio.h>
int mystrstr(char *,char *);
int main()
{
char *s1="123bc123abcabcd1234wx",*s2="456";
int c =mystrstr(s1,s2);
if(c==-1)
printf("String is not found in the main string\n");
else
printf("String starts from index: %d\n",c);
}
int mystrstr(char *ps1,char *ps2)
{
static int i=0,j=0;
if(ps1[i]==ps2[j]&&ps2[j]!='\0')
{
i++;j++;
return mystrstr(ps1,ps2);
}
else if(j!=0)
{
if(ps2[j]=='\0')
return i-j;
else
{
j=0;
return mystrstr(ps1,ps2);
}
}
else if(ps1[i]=='\0')
return -1;
else
{
i++;
return mystrstr(ps1,ps2);
}
}