Матч 349, Поиск документа (DocumentSearch)

Дивизион 2, Уровень 1

Необходимо определить, сколько раз заданное слово или выражение встречается в тексте. При этом не следует подсчитывать перекрывающиеся встречи. Например, в тексте "abababa", слово "ababa" встречается с нулевой и со второй позиции. Поэтому при подсчете следует учитывать только одну из этих встреч, так как они перекрываются.

Сначала следует найти конкатенацию всех строк в массиве doc. Затем найти в нем количество неперекрывающихся встреч слова search.

Класс: DocumentSearch

Метод: int nonIntersecting(vector<string> doc, string search)

Ограничения: doc содержит от 1 до 50 элементов, doc[i] и search содержит от 1 до 50 символов ‘a’ – ‘z’ и пробелов.

Вход. Массив строк doc.

Выход. Количество раз, которое встречается в тексте слово search. Перекрывающиеся встречи слова search не учитывать.

Пример входа

doc	search
{“ababababa”}	“ababa”
{“ababababa”}	“aba”
{“aaa”,“aa”,“a”,“a”}	“aa”

Пример выхода

1

2

3

РЕШЕНИЕ

обработка строк

Совершим конкатенацию всех строк из массива doc в строку s. Ищем первую позицию pos, с которой встречается слово search в тексте s. Удаляем из s подстроку с нулевого по pos + search.size() - ый символ. Подсчитываем количество удалений в переменной c. Повторяем процесс поиска и удаления, пока s содержит в себе search.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

class DocumentSearch

{

public:

int nonIntersecting(vector<string> doc, string search)

{

string s;

int i, pos, c;

for(i = c = 0; i < doc.size(); i++) s = s + doc[i];

while((pos = s.find(search)) >= 0)

s.erase(0,pos + search.size()), c++;

return c;

}

};