Mail.Ru Cup 2018 Раунд 3 |
---|
Закончено |
Один из друзей Аркадия работает на огромном радиотелескопе. Несколько десятилетий назад телескоп послал сигнал $$$s$$$ в соседнюю галактику. Кто бы мог подумать, но недавно от инопланетян пришёл ответ — сигнал $$$t$$$! Учёные хотят проверить, есть ли сходство между сигналами $$$s$$$ и $$$t$$$ или нет.
Исходный сигнал $$$s$$$ был последовательностью нулей и единиц (все знают, что битовая запись является межгалактическим стандартом). Но полученный сигнал $$$t$$$, однако, выглядит более замысловато, чем $$$s$$$. Однако учёные не сдались и представили $$$t$$$ как последовательность латинских букв. Учёные считают, что $$$s$$$ и $$$t$$$ похожи, если можно заменить все нули в $$$s$$$ на некоторую строку $$$r_0$$$, а все единицы в $$$s$$$ на некоторую иную строку $$$r_1$$$ так, что получится строка $$$t$$$. Строки $$$r_0$$$ и $$$r_1$$$ должны быть различными и не пустыми.
Помогите другу Аркадия и посчитайте количество возможных замен нулей и единиц (то есть количество пар строк $$$r_0$$$ и $$$r_1$$$), которые превращают $$$s$$$ в $$$t$$$.
Первая строка содержит строку $$$s$$$ ($$$2 \le |s| \le 10^5$$$), задающую исходный сигнал и состоящую только из нулей и единиц.
Вторая строка содержит строку $$$t$$$ ($$$1 \le |t| \le 10^6$$$), состоящую только из строчных латинских букв и задающую полученный сигнал.
Гарантируется, что строка $$$s$$$ содержит хотя бы один «0» и хотя бы одну «1».
Выведите одно целое число — количество пар строк $$$r_0$$$ и $$$r_1$$$, которые переводят $$$s$$$ в $$$t$$$.
В случае, если ни одной подходящей пары нет, выведите $$$0$$$.
01 aaaaaa
4
001 kokokokotlin
2
В первом примере возможные пары $$$(r_0, r_1)$$$ выглядят следующим образом:
Пара «aaa», «aaa» не разрешена, так как $$$r_0$$$ и $$$r_1$$$ должны быть различными.
Во втором примере возможны следующие пары:
Название |
---|