Находит ли строка итеративную подстроку?

Question

У меня есть строка S. Как я могу найти, если строка следует S = nT.

Примеры:
Функция должна возвращать true, если
1) S = "abab"
2) S = "abcdabcd"
3) S = "abcabcabc"
4) S = "zzxzzxzzx"

Но если S = ​​"abcb", возвращается false.

Iхотя, возможно, мы можем повторно вызвать KMP для подстрок S и затем решить.

например: для "abab": вызвать KMP для "a".он возвращает 2 (два экземпляра).теперь 2 * len ("a")! = len (s)
вызов KMP на "ab".он возвращает 2. теперь 2 * len ("ab") == len (s), так что верните true

Можете ли вы предложить какие-нибудь лучшие алгоритмы?

Answer 1

Я могу думать об эвристическом вызове KMP только для подстроки, если Len (исходная строка) / Len of (подстрока) является положительным целым числом.

Также максимальная длина подстроки должна быть меньше N / 2.

EDIT

Используя эту эвристику, я написал следующий код на python, потому что мой C на данный момент ржавый

oldstr='ABCDABCD'    

for i in xrange(0,len(oldstr)/2):
       newslice=oldstr[0:i+1]
         if newslice*(len(oldstr)/len(newslice)) == oldstr:
             print 'pattern found', newslice
             break

Answer 2

На самом деле вам нужно заботиться только о проверке длины подстроки, равной полной длине строки , деленной на простое число .Причина в том, что если S содержит n копий T, а n не является простым, тогда n = ab, и поэтому S фактически также содержит копии bT (где «bT» означает «T повторено b раз»).Это расширение ответа anijhaw .

int primes[] = { 2, 3, 5, 7, 11, 13, 17 };  /* There are one or two more... ;) */
int nPrimes = sizeof primes / sizeof primes[0];

/* Passing in the string length instead of assuming ASCIIZ strings means we
 * don't have to modify the string in-place or allocate memory for new copies
 * to handle recursion. */
int is_iterative(char *s, int len) {
    int i, j;
    for (i = 0; i < nPrimes && primes[i] < len; ++i) {
        if (len % primes[i] == 0) {
            int sublen = len / primes[i];
            /* Is it possible that s consists of repeats of length sublen? */
            for (j = sublen; j < len; j += sublen) {
                if (memcmp(s, s + j, sublen)) {
                    break;
                }
            }

            if (j == len) {
                /* All length-sublen substrings are equal.  We could stop here
                 * (meaning e.g. "abababab" will report a correct, but
                 * non-minimal repeated substring of length 4), but let's
                 * recurse to see if an even shorter repeated substring
                 * can be found. */
                return is_iterative(s, sublen);
            }
        }
    }

    return len;     /* Could not be broken into shorter, repeated substrings */
}

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

Answer 3

Я не вижу, чтобы алгоритм KMP помог в этом случае.Вопрос не в том, чтобы определить, где начать следующий матч.Кажется, что один из способов сократить время поиска - начать с самой длинной возможности (на половину длины) и работать вниз.Единственные длины, которые необходимо проверить, - это длины, которые равномерно делятся на общую длину.Вот пример в Ruby.Я должен добавить, что я понимаю, что вопрос был помечен как C, но это был простой способ показать алгоритм, о котором я думал (и позволил мне проверить, что он работает).

Answer 4

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

Мы можем сделать это лучше, используя наблюдение, что для подстроки должен быть действительный кандидат len(str) % len(substr) == 0.Это можно вывести из постановки задачи.

Вот полный код:

bool isRational(const string &str){
    int len = str.length();
    const auto &factors = getFactors(len); // this would include 1 but exclude len
    // sort(factors.begin(), factors.end()); To get out of the loop faster. Why? See https://stackoverflow.com/a/4698155/1043773
    for(auto iter = factors.rbegin(); iter != factors.rend(); ++iter){
        auto factor = *iter;
        bool result = true;
        for(int i = 0; i < factor && result; ++i){
            for(int j = i + factor; j < len; j += factor, ++cntr){
                if (str[i] != str[j]) { result = false; break; }
            }
        }

        if (result) { return true;}
    }
    return false;
}

Обратите внимание, что существует более быстрое изменение с точки зрения сложности времени, при котором используется KMP.

Вышеприведенный алгоритм O(N * factorCount(N)) Но хорошо в этом алгоритме то, что он может выручить намного быстрее, чем алгоритм KMP.Также количество факторов не сильно растет.

Вот график [i, factorCount(i)] for i <= 10^6

Вот как работает алгоритм по сравнению с алгоритмом KMP. Красный график - O (N * factorCount (N)) и Синий - O (N) KMP

Код KMP выбирается из здесь

Answer 5

Вы можете построить массив суффиксов строки, отсортировать его.
Теперь ищите серии когда-либо удваивающихся суффиксов, и когда вы достигнете одного, который будет размером всей строки (S), первый в серии будетдать вам T.

Например:

abcd <-- T
abcdabcd <-- S
bcd
bcdabcd
cd
cdabcd
d
dabcd

x
xzzx
xzzxzzx
zx
zxzzx
zxzzxzzx
zzx <-- T
zzxzzx
zzxzzxzzx <-- S

a
apa
apapa
apapapa
pa <-- T
papa
papapa <-- Another T, not detected by this algo
papapapa <-- S

Answer 6

Это код Java, но вы должны понять:

        String str = "ababcababc";
    int repPos = 0;
    int repLen = 0;
    for( int i = 0; i < str.length(); i++ ) {
        if( repLen == 0 ) {
            repLen = 1;
        } else {
            char c = str.charAt( i );
            if( c == str.charAt( repPos ) ) {
                repPos = ++repPos % repLen;
            } else {
                repLen = i+1;
            }
        }
    }

Возвращает длину самого короткого повторяющегося фрагмента или длину строки, если нет повторений.

Answer 7

Попробуйте это:

    char s[] = "abcabcabcabc";
int nStringLength = strlen (s);
int nMaxCheckLength = nStringLength / 2;
int nThisOffset;
int nNumberOfSubStrings;
char cMustMatch;
char cCompare;
BOOL bThisSubStringLengthRepeats;
// Check all sub string lengths up to half the total length
for (int nSubStringLength = 1;  nSubStringLength <= nMaxCheckLength;  nSubStringLength++)
{
    // How many substrings will there be?
    nNumberOfSubStrings = nStringLength / nSubStringLength;

    // Only check substrings that fit exactly
    if (nSubStringLength * nNumberOfSubStrings == nStringLength)
    {
        // Assume it's going to be ok
        bThisSubStringLengthRepeats = TRUE;

        // check each character in substring
        for (nThisOffset = 0;  nThisOffset < nSubStringLength;  nThisOffset++)
        {
            // What must it be?
            cMustMatch = s [nThisOffset];

            // check each substring's char in that position
            for (int nSubString = 1;  nSubString < nNumberOfSubStrings;  nSubString++)
            {
                cCompare = s [(nSubString * nSubStringLength) + nThisOffset];
                // Don't bother checking more if this doesn't match
                if (cCompare != cMustMatch)
                {
                    bThisSubStringLengthRepeats = FALSE;
                    break;
                }
            }

            // Stop checking this substring
            if (!bThisSubStringLengthRepeats)
            {
                break;
            }
        }

        // We have found a match!
        if (bThisSubStringLengthRepeats)
        {
            return TRUE;
        }
    }
}

// We went through the whole lot, but no matches found
return FALSE;

Answer 8

Полагаю, вы могли бы попробовать следующий алгоритм:

Позволяет L быть возможной длиной подстроки, которая генерирует исходное слово.Для L от 1 до strlen(s)/2 проверьте, получает ли первый символ все позиции L*i для i от 1 до strlen(s)/L.Если это так, то это может быть возможным решением, и вы должны проверить его с помощью memcmp, если нет, попробуйте следующий L.Конечно, вы можете пропустить некоторые L значения, которые не делятся strlen(s).