Eşzamanlı Yankı#13118
Küçük İngiliz harflerinden oluşan iki ve dizgisi veriliyor.
Boş olmayan bir dizgisi için, onun içindeki tüm geçtiği yerlerin başlangıç konumları p_1<p_2<\ldots<p_k, içindeki tüm geçtiği yerlerin başlangıç konumları ise q_1<q_2<\ldots<q_m olsun. Konumlar 'den başlayarak numaralandırılır.
Eğer k=m\ge 3 ise ve
koşulunu sağlayan bir tam sayısı varsa, dizgisine eşzamanlı diyoruz.
Başka bir deyişle, dizgisinin bir dizgideki tüm geçtiği yerler aynı miktarda kaydırıldığında, diğer dizgideki tüm geçtiği yerlerle çakışır. Kaydırma miktarı pozitif, negatif veya sıfır olabilir ve farklı dizgileri için farklı olabilir.
Farklı, boş olmayan eşzamanlı dizgilerin sayısını bulun. İki dizgi, uzunlukları farklıysa veya en az bir karakterde birbirinden ayrılıyorsa farklı kabul edilir. Geçtiği yerler çakışabilir.
Birinci satırda , ikinci satırda verilir (1\le |s|,|t|\le 2\cdot 10^5). Her iki dizgi de yalnızca küçük İngiliz harflerinden oluşur.
Bir tam sayı — farklı, boş olmayan eşzamanlı dizgilerin sayısını yazdırın.
Örnek 1
Örnek 2
Örnek 3
Birinci örnekte uygun olan altı dizgi şunlardır: a, b, c, ab, bc ve abc. Özellikle, abc dizgisi içinde konumlarında, içinde ise konumlarında geçer; bu nedenle kaydırma miktarı d=1 olur.
İkinci örnekte a her iki dizgide de üç kez geçer, ancak başlangıç konumları ve şeklindedir. Tek bir kaydırma ile bu kümeleri çakıştırmak mümkün değildir. Her iki dizgide de en az üç kez geçen başka bir dizgi yoktur.
Üçüncü örnekte uygun dizgiler a, aa ve aaa dizgileridir.
Alt görev ( puan): |s|,|t|\le 12.
Alt görev ( puan): |s|,|t|\le 100.
Alt görev ( puan): |s|,|t|\le 2000.
Alt görev ( puan): s=t.
Alt görev ( puan): \min(|s|,|t|)\le 200.
Alt görev ( puan): ek kısıt yoktur.