1 Тема від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 286
    • Репутація: 13020

Тема: Порівняння регулярок

Зіткнувся з цікавою задачею. Є дві маски файлів (спрощений регулярний вираз, де є всього два особливих символи: * означає "0 чи більше будь-яких символів" та "? означає рівно 1 будь-який символ"). Треба встановити, чи можуть вони в принципі бути сумісними, тобто чи в принципі може існувати стрічка (назва файлу), що задовільняє обом маскам. Наприклад:
file.* та *.doc - сумісні, бо можливі file.doc, file.1.doc і т.д.
*.doc та *.docx - несумісні
*.doc та *.doc* - сумісні
var*.d?? та ??r.*c - сумісні (var.doc)

Можливо, хто зустрічав алгоритм для цього? А для звичайних регулярних виразів? Чи, можливо, навіть алгоритм для злиття регулярок в одну?

Подякували: 0xDADA11C7, leofun01, P.Y.3

koala вебсайт

2 Відповідь від leofun01 Востаннє редагувалося leofun01 (21.03.2020 02:45:30)

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 015
    • Репутація: 2608

Re: Порівняння регулярок

Трохи переформулюю під себе (якщо десь буде помилка, то виправляйте).

Потрібно написати функцію, яка приймає 2 стрічки ("спрощені регулярки") і повертає bool

  • true , якщо існує стрічка, яка попадає під "регулярку_1" і попадає під "регулярку_2";

  • false, в іншому випадку.

Є така ідея:
Проходимо по символах (двох стрічок) з початку і з кінця поки не дійдемо до символу '*' і порівнюємо ті 2 символи:

▼Приклад 1

Проходимо з початку стрічок

[*]. d o c 
[*]. d o c x

Дійшли до '*', тому переходимо до проходження з кінця стрічок

   * . d o[c]
 * . d o c[x]

'c' != '?' && 'x' != '?' && 'c' != 'x', тому повертаємо false.

▼Приклад 2

Проходимо з початку

[*]. d o c 
[*]. d o c *

Дійшли до '*', переходимо до напрямку з кінця

   * . d o[c]
 * . d o c[*]

Дійшли до '*', тому переходимо до ... тут треба подумати як дальше перевіряти.
Мені здається на цьому етапі можна вертати true. Треба пошукати контр приклад.

upd: Якось так

public static bool CommonStringExist(string s1, string s2) {
    int i = 0;
    while(i < s1.Length && i < s2.Length) {
        char c1 = s1[i], c2 = s2[i];
        if(c1 == '*' || c2 == '*') break;
        if(c1 != '?' && c2 != '?' && c1 != c2) return false;
        ++i;
    }
    if(i == s1.Length) {
        while(i < s2.Length && s2[i] == '*') ++i;
        return i == s2.Length;
    }
    if(i == s2.Length) {
        while(i < s1.Length && s1[i] == '*') ++i;
        return i == s1.Length;
    }
    i = s1.Length;
    int j = s2.Length;
    while(--i >= 0 && --j >= 0) {
        char c1 = s1[i], c2 = s2[j];
        if(c1 == '*' || c2 == '*') break;
        if(c1 != '?' && c2 != '?' && c1 != c2) return false;
    }
    if(i < 0) {
        while(j >= 0 && s2[j] == '*') --j;
        return j < 0;
    }
    if(j < 0) {
        while(i >= 0 && s1[i] == '*') --i;
        return i < 0;
    }
    return true;
}
Подякували: P.Y., koala2

leofun01 вебсайт

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 286
    • Репутація: 13020

Re: Порівняння регулярок

Гм.
s1="a*b*c"
s2="adc"
Здається, не спрацює.

Подякували: leofun011

koala вебсайт

4 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 015
    • Репутація: 2608

Re: Порівняння регулярок

Одностороній прохід з рекурсією, пробуйте

public static bool CommonStringExist(string s1, string s2) {
    int i = 0;
    while(i < s1.Length && i < s2.Length) {
        char c1 = s1[i], c2 = s2[i];
        if(c1 == '*' || c2 == '*') break;
        if(c1 != '?' && c2 != '?' && c1 != c2) return false;
        ++i;
    }
    bool asterix1 = i < s1.Length && s1[i] == '*';
    bool asterix2 = i < s2.Length && s2[i] == '*';
    int j = i;
    while(i < s1.Length && s1[i] == '*') ++i;
    while(j < s2.Length && s2[j] == '*') ++j;
    if(i == s1.Length && j == s2.Length) return true;
    if(asterix2)
        for(int m = i; m <= s1.Length; ++m)
            if(CommonStringExist(s1.Substring(m), s2.Substring(j)))
                return true;
    if(asterix1)
        for(int n = j; n <= s2.Length; ++n)
            if(CommonStringExist(s1.Substring(i), s2.Substring(n)))
                return true;
    return false;
}
Подякували: koala1

leofun01 вебсайт