Решение задачи Строки с Acmp

С пояснением   Просмотров: 4090

Циклическим сдвигом строки s называется строка sksk+1sk+2…s|s|s1s2…sk-1 для некоторого k, здесь |s| - длина строки s. Подстрокой строки s называется строка sisi+1…sj-1sj для некоторых i и j. Вам даны две строки a и b. Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b.

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s, s1;
    int k = 0;
    cin >> s >> s1;
    set<string> a;
    for(int i = 0; i < s1.size(); ++i){
        a.insert(s1.substr(s1.size() - i - 1) + s1.substr(0, s1.size() - i - 1) );
    }
    for(auto i: a){
        int pos = s.find(i);
        while(pos + 1){
            ++k;
            pos = s.find(i, pos +  1);
        }
    }
    cout << k;
    return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Разберём первый пример сайта ACMP:
abcabc
abc
1) перебираем сдвиги строки s1: abc, cab, bca
2) Проверяем каждый из них, если встречается то ++k;
В данном примере: "abc" встречается "abcabc" - 2 раза, cab - 1 раз, bca - 1 раз.
Итого: 4 раза
Надеюсь, вы поняли алгоритм:-))


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp