4

Вроде очень легкая задача, но я копаюсь уже час и не пойму как сделать.

У меня есть строка 3 символа, "abc", нужно чтобы регулярные выражения пропускали только эти 3 символа в любом порядке (abc, bca, cab ...), но не пропускали повторение этих символов (aab, ccc).

Пытался сделать что то с исключением предыдущей группы захвата (скорее всего не правильно), но оно все равно пропускает повторяющиеся символы ^([abc])([abc][^(?(1))])([abc][^(?(1))][^(?(2))])$

0

2 ответа 2

3

Не думаю что у вас будет что-то проще полного перебора вариантов:

/abc|acb|bac|bca|cab|cba/
/a(bc|cb)|b(ac|ca)|c(ab|ba)/

А думаю я так потому что классическое регулярное выражение отображается на конечный автомат, у которого фиксированный объём памяти, которого не хватит чтобы посчитать число вхождений каждого символа. Следовательно, вам понадобится регулярное выражение длина которого сравнима с суммарной длиной всех ответов. То есть, полного перебора не избежать.

С другой стороны в разных машинах регулярных выражений могут быть разные расширения, которые могут преодолеть "барьер конечной памяти". Не уверен.

1
  • Понял, тогда сделаю перебором, спасибо! 22 июл 2022 в 12:43
3

Используйте

([abc])(?!\1)([abc])(?!\1|\2)[abc]

Или в Qt 6, в QRegularExpression, где есть поддержка синтаксиса PCRE:

([abc])(?!\1)((?1))(?!\1|\2)(?1)

См. пример использования выражения #1 / пример использования выражения #2.

Подробности:

  • ([abc]) - Подмаска №1: a, b или c
  • (?!\1) - сразу после текущей позиции не должно быть текста, захваченного первой подмаской
  • ([abc]) - Подмаска №2: a, b или c
  • (?!\|1\2) - сразу после текущей позиции не должно быть текста, захваченного первой и второй подмаской
  • [abc] - a, b или c

(?1) используется вместо повтора шаблона первой подмаски.

Полный перебор вариантов

Не делайте это вручную, если у вас список из сотен или тысяч строк. Постройте регулярное выражение на основе префиксного дерева с помощью специальных библиотек или пользуясь кодом ниже. Нажмите Выполнить код, вставьте свои слова (разделитель - запятая или перенос строки) в текстовое поле и нажмите кнопку Создать:

!function(){return function t(e,n,r){function i(s,u){if(!n[s]){if(!e[s]){var c="function"==typeof require&&require;if(!u&&c)return c(s,!0);if(o)return o(s,!0);var f=new Error("Cannot find module '"+s+"'");throw f.code="MODULE_NOT_FOUND",f}var a=n[s]={exports:{}};e[s][0].call(a.exports,function(t){return i(e[s][1][t]||t)},a,a.exports,t,e,n,r)}return n[s].exports}for(var o="function"==typeof require&&require,s=0;s<r.length;s++)i(r[s]);return i}}()({1:[function(t,e,n){(function(t){(function(){!function(r){var i="object"==typeof n&&n,o="object"==typeof e&&e&&e.exports==i&&e,s="object"==typeof t&&t;s.global!==s&&s.window!==s||(r=s);var u={},c=u.hasOwnProperty,f=function(t,e){var n;for(n in t)c.call(t,n)&&e(n,t[n])},a=u.toString,p={'"':'\\"',"'":"\\'","\\":"\\\\","\b":"\\b","\f":"\\f","\n":"\\n","\r":"\\r","\t":"\\t"},_=/["'\\\b\f\n\r\t]/,h=/[0-9]/,l=/[ !#-&\(-\[\]-~]/,d=function(t,e){var n,r,i={escapeEverything:!1,quotes:"single",wrap:!1,es6:!1,json:!1,compact:!0,indent:"\t",__indent__:""},o=e&&e.json;o&&(i.quotes="double",i.wrap=!0),n=i,"single"!=(e=(r=e)?(f(r,function(t,e){n[t]=e}),n):n).quotes&&"double"!=e.quotes&&(e.quotes="single");var s,u,c,g="double"==e.quotes?'"':"'",y=e.compact,v=e.indent,b=y?"":"\n",j=!0;if(o&&t&&("function"==typeof(c=t.toJSON)||"[object Function]"==a.call(c))&&(t=t.toJSON()),!function(t){return"string"==typeof t||"[object String]"==a.call(t)}(t))return function(t){return"[object Array]"==a.call(t)}(t)?(u=[],e.wrap=!0,s=e.__indent__,v+=s,e.__indent__=v,function(t,e){for(var n=t.length,r=-1;++r<n;)e(t[r])}(t,function(t){j=!1,u.push((y?"":v)+d(t,e))}),j?"[]":"["+b+u.join(","+b)+b+(y?"":s)+"]"):function(t){return"[object Object]"==a.call(t)}(t)?(u=[],e.wrap=!0,s=e.__indent__,v+=s,e.__indent__=v,f(t,function(t,n){j=!1,u.push((y?"":v)+d(t,e)+":"+(y?"":" ")+d(n,e))}),j?"{}":"{"+b+u.join(","+b)+b+(y?"":s)+"}"):o?JSON.stringify(t)||"null":String(t);var w,m,x=t,q=-1,E=x.length;for(u="";++q<E;){var S=x.charAt(q);if(e.es6&&(w=x.charCodeAt(q))>=55296&&w<=56319&&E>q+1&&(m=x.charCodeAt(q+1))>=56320&&m<=57343)u+="\\u{"+(1024*(w-55296)+m-56320+65536).toString(16).toUpperCase()+"}",q++;else{if(!e.escapeEverything){if(l.test(S)){u+=S;continue}if('"'==S){u+=g==S?'\\"':S;continue}if("'"==S){u+=g==S?"\\'":S;continue}}if("\0"!=S||o||h.test(x.charAt(q+1)))if(_.test(S))u+=p[S];else{var O=S.charCodeAt(0).toString(16).toUpperCase(),A=O.length>2||o,N="\\"+(A?"u":"x")+("0000"+O).slice(A?-4:-2);u+=N}else u+="\\0"}}return e.wrap&&(u=g+u+g),u};d.version="0.5.0","function"==typeof define&&"object"==typeof define.amd&&define.amd?define(function(){return d}):i&&!i.nodeType?o?o.exports=d:i.jsesc=d:r.jsesc=d}(this)}).call(this)}).call(this,"undefined"!=typeof global?global:"undefined"!=typeof self?self:"undefined"!=typeof window?window:{})},{}],2:[function(t,e,n){var r=t("jsesc"),i=function(){"use strict";var t=function(){return this instanceof t?(this._num_phrases_in_trie=0,this._trie={},this):new t};return t.prototype.add=function(t){if(t instanceof Array&&t.forEach(this.add,this),t=this._coerce_to_string(t),!this._is_phrase_valid(t))return this;if(this.contains(t))return this;var e=this._trie;return t.split("").forEach(function(t){t in e?e=e[t]:(e[t]={},e=e[t])},this),e.end=!0,this._num_phrases_in_trie++,this},t.prototype.toRegExp=function(){if(0!==this._num_phrases_in_trie){var t=this.toString();return new RegExp(t)}},t.prototype.toString=function(){if(0!==this._num_phrases_in_trie){var t=function(e,n){var r=Object.keys(e),i=[],o=[],s=!1;return r.forEach(function(u){var c;"end"!==u?(c=this._quotemeta(u)+t(e[u],n),(r.length>1?[].push.bind(i):[].push.bind(o))(c)):s=!0},n),n._to_regex(i,o,s)};return t(this._trie,this)}},t.prototype._to_regex=function(t,e,n){var r="";return t.length>0?1===t.length?r+=t[0]:t.every(function(t){return 1===t.length})?r+="["+t.join("")+"]":r+="(?:"+t.join("|")+")":e.length>0&&(r+=e[0]),n&&r&&(1===r.length?r+="?":r="(?:"+r+")?"),r},t.prototype.contains=function(t){if(!this._is_phrase_valid(t)&&this._num_phrases_in_trie>0)return!1;var e=this._trie;try{return t.split("").forEach(function(t){e=e[t]}),e.hasOwnProperty("end")&&!0===e.end}catch(t){}return!1},t.prototype._coerce_to_string=function(t){return"number"!=typeof t||isNaN(t)||(t=t.toString()),t},t.prototype._is_phrase_valid=function(t){return"string"==typeof t&&t.length>0},t.prototype._quotemeta=function(t){return this._is_phrase_valid(t)?t.replace(/([\t\n\f\r\\\$\(\)\*\+\-\.\?\[\]\^\{\|\}])/g,"\\$1").replace(/[^\x20-\x7E]/g,r):t},t}();e.exports=i},{jsesc:1}],3:[function(t,e,n){$(document).ready(function(){$("#run").click(function(e){e.preventDefault(),$("#result").html("");const n=$("#inputdata").val().match(/[^\r\n,]+/g);let r=new(t("regex-trie"));r.add(n);const i=r.toRegExp();$("#result").append("<b>"+i.source.replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;")+"</b><br/>")})})},{"regex-trie":2}]},{},[3]);
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<form>
  <p>Вставьте список слов, разделённых запятой или переносом строки, в окошко снизу и нажмите кнопку <i>Создать</i>.</p>
  <textarea id="inputdata"></textarea>
  <br/>
  <button id="run">Создать</button>
  <pre><code id="result" /></pre>
</form>

1
  • спасибо за ответ, но данная запись просто длиннее оказывается, проще как ответил @stanislav-volodarskiy 22 июл 2022 в 22:33

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.