TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4151
  • 問題
  • P4151【Tjoi2016&Heoi2016】字符串
    制限 : 時間制限 : 20000 MS   メモリ制限 : 131572 KB
    問題説明

    佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s,和m个问题。佳媛姐姐必须正确回答这m个问题,才能打开箱子拿到礼物,升职加薪,出任CEO,嫁给高富帅,走上人生巅峰。每个问题均有a,b,c,d四个参数,问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少?佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢?

    入力形式

    输入的第一行有两个正整数n,m,分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行,每行有4个数a,b,c,d,表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。

    出力形式

     对于每一次询问,输出答案。

    サンプル入力

    5 5
    aaaaa
    1 1 1 5
    1 5 1 1
    2 3 2 3
    2 4 2 3
    2 3 2 4

    サンプル出力

    1
    1
    2
    2
    2

    ヒント

    1<=n,m<=100,000,字符串中仅有小写英文字母,a<=b,c<=d,1<=a,b,c,d<=n


    ソース  感谢spark向dalao要数据