Количество подстрок, не содержащих заданные строки (большое ограничение)

Поскольку одинаковые подстроки, начинающиеся с разных позиций, считаются разными подстроками, максимальное количество подстрок в строке длины n равно n*(n + 1)/2. (n подстрок, начинающихся с позиции 0, n-1 подстрок, начинающихся с позиция 1 и так далее).

Если уродливая строка содержится в подстроке длины q, начинающейся с позиции p, все подстроки, начинающиеся с p и имеющие длину > q, также будут содержать эту уродливую строку.

Если уродливая строка длиннее самой подстроки, она не будет совпадать.

Моя первая попытка будет выглядеть так:

String ugly[]; // is provided somehow; at most 500000 with max length of 500000
String student; // the String to cut into substrings, max length 100000
long num = 0;

ugly.sort(); // by length

for (int start = 0; start < student.size() - 1, ++start) {
    for (int end = start + 1; end < student.size(); ++end) {
        String s = student.substr(start, end);
        int lgth = s.size();
        int u = 0;
        while (lgth >= ugly[u].size()) {
            if (s.contains(ugly[u])) break;
            ++u;
        }
        if (lgth < ugly[u].size()) {
            ++num; // we checked all potentially matching uglies
        } else {
            break; // leave the inner loop and 
                   // start with the next position
        }
    }
}

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

Если у меня есть строка student и уродливая строка длины p, которая где-то совпадает, строка student может быть разделена на две части: первая часть, которая заканчивается первыми p-1 символами уродливой строки, и вторая часть, которая начинается с последние символы p-1 уродливой строки.

Это можно повторять до тех пор, пока уродливая строка нигде не будет совпадать. Затем у нас есть несколько подстрок и уродливая строка, которая не соответствует ни одной из них. Следовательно, эту уродливую строку можно отбросить.

Повторяя это для всех уродливых строк, вы получите список «самых длинных» подстрок, которые не соответствуют ни одной из уродливых строк. Теперь вы можете перебрать этот список и добавить длину * (длина + 1)/2 к конечному результату.

Так это будет выглядеть

String ugly[]; // as before
String student; // as before
long num = 0;
Vector substrs = new Vector();

ugly.sort(); // by length
substrs.add(student);

void splitStr(String str2split, String pattern, Vector result)
{
    if (str2split.size() < pattern.size()) {
        result.add(str2split);
        return;
    } else {
        int pos = str2split.contains(pattern); // returns position, -1 if not found
        if (pos >= 0) { // found
            String s1 = str2split.substr(0, pos + pattern.size() - 1);
            String s2 = str2split.substr(pos + 1, str2split.size());
            // add s1 and repeat split on s2
            result.add(s1);
            splitStr(s2, pattern, result);
        } else {
            // not found, entire string is ok
            result.add(str2split);
        }
    }
}

for (int u = 0; u < ugly.size(); ++u) {
    Vector newSubstrs = new Vector();
    String ugly2test = ugly[u];
    for (int i = 0; i < substrs.size(); ++i) {
        String t = substrs.get(i);
        splitStr(t, ugly2test, newSubstrs);
    }
    substrs = newSubstrs;
}

for (int i = 0; i < substrs.size(); ++i) {
    String s = substrs.get(i);
    num += s.size() * (s.size() + 1) / 2;
}

Примечание: это в основном идея. Я не тестировал какой-либо код (который похож на Java, но, вероятно, не будет компилироваться), я только перевел свою идею простого текста в какой-то псевдокод.