AT_tenka1_2014_final_e 田端でバタバタ

[problemUrl]: https://atcoder.jp/contests/tenka1-2014-final/tasks/tenka1_2014_final_e 繰り返し文字列とは、ある空でない文字列 $ A $ があって $ A+A $ の形で表される文字列のことを表します。言語学では畳語ともいいます。日本語は畳語が非常に多く、通常の文章でも頻繁に出現します。今回はこれを数えてみたいと思います。 小文字アルファベットからなる文字列 $ S $ と $ Q $ 個のクエリ $ [a_i,b_i] $ が与えられます。$ S[a_i,b_i] $ の全ての空でない部分文字列のうち、繰り返し文字列となっているものの長さの和を求めてください。同じ文字列が複数存在する場合も、それぞれ別の物として考えてください。 なお、文字列 $ A $ と $ B $ に対して、連結したものを $ A+B $ と表します。また $ S[x,y] $ とは、文字列 $ S $ の $ x $ 文字目から $ y $ 文字目までを切り取った部分文字列を表します。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ Q $ $ a_1 $ $ b_1 $ ... $ a_Q $ $ b_Q $ - $ 1 $ 行目には、文字列 $ S\ (1\ ≦\ |S|\ ≦\ 100000) $ が与えられる。（$ |S| $ は文字列 $ S $ の長さを表す） - $ 2 $ 行目には、クエリの数を表す整数 $ Q\ (1\ ≦\ Q\ ≦\ 100000) $ が与えられる。 - $ 3 $ 行目から $ Q $ 行は、クエリの情報が与えられる。 このうち $ i\ (1\ ≦\ i\ ≦\ Q) $ 行目には、 $ i $ 番目のクエリの情報を表す整数 $ a_i,\ b_i\ (1\ ≦\ a_i\ ≦\ b_i\ ≦\ |S|) $ が、スペース区切りで与えられる。

各クエリに対する答えを、 $ 1 $ 行ずつ $ Q $ 行で出力せよ。出力の末尾には改行をいれること。

### 部分点 $ 1\ ≦\ |S|\ ≦\ 1000 $ のテストケースに全て正解した場合 、部分点として $ 100 $ 点が与えられる。 $ 1\ ≦\ |S|\ ≦\ 20000 $ のテストケースに全て正解した場合 、部分点としてさらに $ 100 $ 点が与えられる。 全てのテストケースに正解すると、さらに $ 150 $ 点が与えられる。 ### Sample Explanation 1 `koko`と`pyonpyon`が繰り返し文字列に相当します。 $ 1 $ つ目のクエリでは、`kokoropyonpyon`について考えます。`koko`、`pyonpyon`の $ 2 $つの繰り返し文字列が存在するので、答えは $ 12 $ です。 $ 2 $ つ目のクエリでは、`okoropyonpyon`について考えます。`pyonpyon`が存在するので、答えは $ 8 $ です。 $ 3 $ つ目のクエリでは、`kokoropyonpyo`について考えます。`koko`が存在するので、答えは $ 4 $ です。 ### Sample Explanation 2 `attatt`, `ttatta`, `tt`, `tt`が、繰り返し文字列に該当します。`tt` $ 2 $ 個は別物とします。 ### Sample Explanation 3 大量の繰り返し文字列が発生するケースが存在することに注意してください。