Ответ 1

Это классическая проблема динамическое программирование (и обычно не решается с помощью регулярных выражений).

Моя наивная реализация (подсчет 3 для каждого 2 после каждого 1) работает в течение часа, и это не делается.

Это будет исчерпывающий подход к поиску, который выполняется в экспоненциальном времени. (Я удивлен, что он работает несколько часов).

Здесь предлагается решение для динамического программирования:

Схема для рекурсивного решения:

(Извинения за длинное описание, но каждый шаг действительно прост, так что несите меня; -)

• Если подпоследовательность пуста, найдено совпадение (цифры не должны совпадать!), и мы возвращаем 1

• Если последовательность ввода пуста, мы исчерпали наши цифры и не можем найти совпадение, поэтому возвращаем 0

• (Ни последовательность, ни подпоследовательность не пусты.)

• (Предположим, что " abcdef" обозначает входную последовательность, а " xyz" обозначает подпоследовательность.)

• Установите result в 0

• Добавьте к result количество совпадений для bcdef и xyz (т.е. отбросьте первую цифру ввода и рекурсию)

• Если первые две цифры совпадают, т.е. a = x

  • Добавьте к result количество совпадений для bcdef и yz (т.е. сопоставьте первую цифру подпоследовательности и рекурсию с остальными цифрами подпоследовательности)
    
    

• Возврат result

Пример

Вот иллюстрация рекурсивных вызовов для ввода 1221/ 12. (Подпоследовательность жирным шрифтом, & middot; представляет собой пустую строку.)

Динамическое программирование

Если реализовать наивно, некоторые (суб-) проблемы решаются несколько раз (& middot;/2, например, на рисунке выше). Динамическое программирование позволяет избежать таких избыточных вычислений, запоминая результаты ранее разрешенных подзадач (обычно в таблице поиска).

В этом конкретном случае мы устанавливаем таблицу с

• [длина последовательности + 1] строк и
• [длина подпоследовательности + 1] столбцы:

Идея состоит в том, что мы должны заполнить количество совпадений для 221/ 2 в соответствующей строке/столбце. После этого мы должны получить окончательное решение в ячейке 1221/ 12.

Мы начинаем заполнять таблицу тем, что мы знаем сразу ( "базовые случаи" ):

• Когда не осталось цифр подпоследовательности, у нас есть 1 полное совпадение:

• Если цифр последовательности не осталось, мы не можем иметь никаких совпадений:

Затем переходим к заполнению таблицы сверху вниз/слева направо в соответствии со следующим правилом:

• В ячейке [row] [col] напишите значение, найденное в [row-1] [col].

  Интуитивно это означает: "Число совпадений для 221/ 2 включает все совпадения для 21/ 2."

• Если последовательность в строке строки и подзаголовке в столбце col начинаться с той же цифры, добавьте значение, найденное в [row-1] [col-1], к значению, только что записанному в [row] [col].

  Интуитивно это означает: "Число совпадений для 1221/ 12 также включает все совпадения для 221/ 12."

Конечный результат выглядит следующим образом:

и значение в нижней правой ячейке действительно 2.

В коде

Не в Python, (мои извинения).

class SubseqCounter {

    String seq, subseq;
    int[][] tbl;

    public SubseqCounter(String seq, String subseq) {
        this.seq = seq;
        this.subseq = subseq;
    }

    public int countMatches() {
        tbl = new int[seq.length() + 1][subseq.length() + 1];

        for (int row = 0; row < tbl.length; row++)
            for (int col = 0; col < tbl[row].length; col++)
                tbl[row][col] = countMatchesFor(row, col);

        return tbl[seq.length()][subseq.length()];
    }

    private int countMatchesFor(int seqDigitsLeft, int subseqDigitsLeft) {
        if (subseqDigitsLeft == 0)
            return 1;

        if (seqDigitsLeft == 0)
            return 0;

        char currSeqDigit = seq.charAt(seq.length()-seqDigitsLeft);
        char currSubseqDigit = subseq.charAt(subseq.length()-subseqDigitsLeft);

        int result = 0;

        if (currSeqDigit == currSubseqDigit)
            result += tbl[seqDigitsLeft - 1][subseqDigitsLeft - 1];

        result += tbl[seqDigitsLeft - 1][subseqDigitsLeft];

        return result;
    }
}

Сложность

Бонус для этого подхода "заполнение в таблице" заключается в том, что тривиально определить сложность. Для каждой ячейки выполняется постоянная работа, и у нас есть столбцы длины последовательности и столбцы длины последовательности. Сложность заключается в том, что O (MN), где M и N обозначают длины последовательностей.

Ответ 2

Отличный ответ, aioobe! в дополнение к вашему ответу, некоторые возможные реализации в Python:

# straightforward, naïve solution; too slow!

def num_subsequences(seq, sub):
    if not sub:
        return 1
    elif not seq:
        return 0
    result = num_subsequences(seq[1:], sub)
    if seq[0] == sub[0]:
        result += num_subsequences(seq[1:], sub[1:])
    return result

# top-down solution using explicit memoization

def num_subsequences(seq, sub):
    m, n, cache = len(seq), len(sub), {}
    def count(i, j):
        if j == n:
            return 1
        elif i == m:
            return 0
        k = (i, j)
        if k not in cache:
            cache[k] = count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
        return cache[k]
    return count(0, 0)

# top-down solution using the lru_cache decorator
# available from functools in python >= 3.2

from functools import lru_cache

def num_subsequences(seq, sub):
    m, n = len(seq), len(sub)
    @lru_cache(maxsize=None)
    def count(i, j):
        if j == n:
            return 1
        elif i == m:
            return 0
        return count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
    return count(0, 0)

# bottom-up, dynamic programming solution using a lookup table

def num_subsequences(seq, sub):
    m, n = len(seq)+1, len(sub)+1
    table = [[0]*n for i in xrange(m)]
    def count(iseq, isub):
        if not isub:
            return 1
        elif not iseq:
            return 0
        return (table[iseq-1][isub] +
               (table[iseq-1][isub-1] if seq[m-iseq-1] == sub[n-isub-1] else 0))
    for row in xrange(m):
        for col in xrange(n):
            table[row][col] = count(row, col)
    return table[m-1][n-1]

# bottom-up, dynamic programming solution using a single array

def num_subsequences(seq, sub):
    m, n = len(seq), len(sub)
    table = [0] * n
    for i in xrange(m):
        previous = 1
        for j in xrange(n):
            current = table[j]
            if seq[i] == sub[j]:
                table[j] += previous
            previous = current
    return table[n-1] if n else 1

Ответ 3

Один из способов сделать это будет с двумя списками. Назовите их Ones и OneTwos.

Пройдите через строку, символ по символу.

• Всякий раз, когда вы видите цифру 1, сделайте запись в списке Ones.
• Всякий раз, когда вы видите цифру 2, перейдите в список Ones и добавьте запись в список OneTwos.
• Всякий раз, когда вы видите цифру 3, перейдите в список OneTwos и выведите a 123.

В общем случае этот алгоритм будет очень быстрым, так как он проходит через строку и несколько проходит через то, что обычно будет намного меньшим списком. Однако патологические случаи убьют его. Представьте себе строку типа 111111222222333333, но каждая цифра повторяется сотни раз.

Ответ 4

from functools import lru_cache

def subseqsearch(string,substr):
    substrset=set(substr)
    #fixs has only element in substr
    fixs = [i for i in string if i in substrset]
    @lru_cache(maxsize=None) #memoisation decorator applyed to recs()
    def recs(fi=0,si=0):
        if si >= len(substr):
            return 1
        r=0
        for i in range(fi,len(fixs)):
            if substr[si] == fixs[i]:
                r+=recs(i+1,si+1)
        return r
    return recs()

#test
from functools import reduce
def flat(i) : return reduce(lambda x,y:x+y,i,[])
N=5
string = flat([[i for j in range(10) ] for i in range(N)])
substr = flat([[i for j in range(5) ] for i in range(N)]) 
print("string:","".join(str(i) for i in string),"substr:","".join(str(i) for i in substr),sep="\n")
print("result:",subseqsearch(string,substr))

вывод (мгновенно):

string:
00000000001111111111222222222233333333334444444444
substr:
0000011111222223333344444
result: 1016255020032

Ответ 5

Моя быстрая попытка:

def count_subseqs(string, subseq):
    string = [c for c in string if c in subseq]
    count = i = 0
    for c in string:
        if c == subseq[0]:
            pos = 1
            for c2 in string[i+1:]:
                if c2 == subseq[pos]:
                    pos += 1
                    if pos == len(subseq):
                        count += 1
                        break
        i += 1
    return count

print count_subseqs(string='3141592653', subseq='123')

Изменить: Это тоже должно быть правильно, если 1223 == 2 и более сложные случаи:

def count_subseqs(string, subseq):
    string = [c for c in string if c in subseq]
    i = 0
    seqs = []
    for c in string:
        if c == subseq[0]:
            pos = 1
            seq = [1]
            for c2 in string[i + 1:]:
                if pos > len(subseq):
                    break
                if pos < len(subseq) and c2 == subseq[pos]:
                    try:
                        seq[pos] += 1
                    except IndexError:
                        seq.append(1)
                        pos += 1
                elif pos > 1 and c2 == subseq[pos - 1]:
                    seq[pos - 1] += 1
            if len(seq) == len(subseq):
                seqs.append(seq)
        i += 1
    return sum(reduce(lambda x, y: x * y, seq) for seq in seqs)

assert count_subseqs(string='12', subseq='123') == 0
assert count_subseqs(string='1002', subseq='123') == 0
assert count_subseqs(string='0123', subseq='123') == 1
assert count_subseqs(string='0123', subseq='1230') == 0
assert count_subseqs(string='1223', subseq='123') == 2
assert count_subseqs(string='12223', subseq='123') == 3
assert count_subseqs(string='121323', subseq='123') == 3
assert count_subseqs(string='12233', subseq='123') == 4
assert count_subseqs(string='0123134', subseq='1234') == 2
assert count_subseqs(string='1221323', subseq='123') == 5

Ответ 6

Как подсчитать все трехчленные последовательности 1..2..3 в массиве цифр.

Быстро и просто

Обратите внимание: нам не нужно НАЙТИ все последовательности, нам нужно только COUNT их. Таким образом, все алгоритмы, которые ищут последовательности, являются чрезмерно сложными.

• Отбросьте каждую цифру, то есть не 1,2,3. Результатом будет char массив A
• Сделать параллельный массив int B из 0. Запустив A с конца, подсчитайте для каждого 2 в число 3 в после них. Поместите эти числа в соответствующие элементы B.
• Сделать параллельным int array C 0's.Running A от конца отсчета для каждого 1 в сумму B после его позиции. Результат помещается в соответствующее место в C.
• Подсчитайте сумму C.

Вот и все. Сложность O (N). Действительно, для обычной строки цифр это займет примерно в два раза больше времени укорачивания строки источника.

Если последовательность будет длиннее, например, членов M, процедура может быть повторена M раз. И сложностью будет O (MN), где N уже будет длиной сокращенной строки источника.

Ответ 7

рзп. O (n) лучше.

Подумайте об этом, построив дерево:

итерация вдоль строки если символ "1", добавьте node в корень дерева. если символ "2", добавьте ребенка на каждый первый уровень node. если символ "3", добавьте ребенка на каждый второй уровень node.

возвращает количество узлов третьего уровня.

это будет неэффективно, поэтому почему бы нам просто не сохранить количество узлов каждой глубины:

infile >> in;
long results[3] = {0};
for(int i = 0; i < in.length(); ++i) {
    switch(in[i]) {
        case '1':
        results[0]++;
        break;
        case '2':
        results[1]+=results[0];
        break;
        case '3':
        results[2]+=results[1];
        break;
        default:;
    }
}

cout << results[2] << endl;

Ответ 8

У меня есть интересное O (N) время и O (M) пространственное решение для этой проблемы.
N - длина текста, а M - длина шаблона, подлежащего поиску. Я объясню вам алгоритм, потому что я реализую в С++.

позволяет предположить, что введенный ввод указан так, как вы указали 3141592653 и последовательность шаблонов, чье число для нахождения равно 123. Сначала я возьму хэш-карту, которая отображает символы в их позиции во входном шаблоне. Я также беру массив размера M, первоначально инициализированный до 0.

    string txt,pat;
    cin >> txt >> pat;
    int n = txt.size(),m = pat.size();
    int arr[m];
    map<char,int> mp;
    map<char,int> ::iterator it;
    f(i,0,m)
    {
        mp[pat[i]] = i;
        arr[i] = 0;
    }

Я начинаю искать элементы со спины и проверять, находится ли каждый элемент в шаблоне или нет. Если этот элемент находится в шаблоне. Я должен что-то сделать.

Теперь, когда я начинаю смотреть со спины, если я нахожу 2 и раньше, я не нашел никаких 3. Это 2 для нас не имеет значения. Поскольку любое 1 найденное после него будет иметь максимальную форму, такая последовательность 12 и 123 не будет сформирована Ryt? думать. Также в настоящее время я нашел 2, и он будет формировать последовательности 123 только с 3 найденными ранее и будет образовывать x-последовательностей, если мы раньше нашли x 3 (если часть последовательности до 2 будет найдена) ryt? Таким образом, полный алгоритм - это когда я нахожу элемент, который присутствует в массиве, я проверяю его позицию j соответственно, в которой он присутствовал в шаблоне (хранится в хэш-карте). Я просто inc increment

 arr[j] += arr[j+1];

означающее, что это будет способствовать последовательности из 3 найденных до этого ryt? и если j найдено m-1, я просто увеличит его

 arr[j] += 1; 

Проверьте фрагменты кода, ниже которых эти

    for(int i = (n-1);i > -1;i--)
    {
        char ch = txt[i];
        if(mp.find(ch) != mp.end())
        {
            int j = mp[ch];
            if(j == (m-1))
                arr[j]++;
            else if(j < (m-1))
                arr[j] += arr[j+1];
            else
                {;}
        }
    }

Теперь рассмотрим факт

каждый индекс я в массиве хранит количество раз, когда подстрока шаблона S [i, (m-1)] появляется как последовательность входной строки Итак, окончательно напечатайте значение arr [0]

    cout << arr[0] << endl;

Код с выходом (уникальные символы в шаблоне) http://ideone.com/UWaJQF

Код с выходом (повторения разрешены символов) http://ideone.com/14DZh7

Extension работает только в том случае, если шаблон имеет уникальные элементы Что, если шаблон имеет уникальные элементы, тогда сложность может стрелять в O (MN) Решение аналогично, не используя DP только тогда, когда появился элемент, присутствующий в шаблоне, мы просто увеличили позицию массива j, соответствующую ему, теперь нам нужно обновить все вхождения этих символов в шаблоне, что приведет к сложности O (N * maxium frequency чартера)

#define f(i,x,y) for(long long i = (x);i < (y);++i)



int main()
{
long long T;
cin >> T;
while(T--)
{
    string txt,pat;
    cin >> txt >> pat;
    long long n = txt.size(),m = pat.size();
    long long arr[m];
    map<char,vector<long long> > mp;
    map<char,vector<long long> > ::iterator it;
    f(i,0,m)
    {
        mp[pat[i]].push_back(i);
        arr[i] = 0;
    }

    for(long long i = (n-1);i > -1;i--)
    {
        char ch = txt[i];
        if(mp.find(ch) != mp.end())
        {
            f(k,0,mp[ch].size())
            {
                long long j = mp[ch][k];
                if(j == (m-1))
                    arr[j]++;
                else if(j < (m-1))
                    arr[j] += arr[j+1];
                else
                    {;}
                }
                }
                }
                cout <<arr[0] << endl;
                }
                 }

может быть расширена аналогично без DP в строках с повторениями, но тогда сложность будет больше O (MN)