結果

問題 No.430 文字列検索
ユーザー po1_UwQ
提出日時 2024-10-12 18:10:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 21,772 bytes
コンパイル時間 5,172 ms
コンパイル使用メモリ 309,164 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-10 01:13:45
合計ジャッジ時間 8,582 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
                                                                                  `  `                     `
                                                                         ` ` ``` `  .... ` ` `` ````` `
                            `                                                `..JyQQHkmHWHQgHHWXaJ-.   `
                                                                      ```` .-HHkMMMM@HMMMHHNH@HkWWma&-.` `
                                                                   `  `..WHH@MMMMMM#MMHMMNWHmgMHMNMMHHHk..``
               `                                                   `` .dHHHMMMM@MMMMMMNKMMMMMHHmWWHHMHHHHe. ```
                            `                                  `   ` .JHMHMMMMMMMMMHHMMMNMHMHHMMHHmHMqHHWWH+
                                                                `` .HNHHHMNM#HMMHHWHHHHHHMMM@HHHHHHHHWHNHkHHh.`
                                                           `    `` (WMMNWMMMMMHHHNqHMM@H@HMM@HHHM@HMHMHMHgkHHh.` `
                                                             `  ` (WHMHMHHHMHM@MHHMHHMMHHMHHMHH@MH@HHMHNWHHkgHb
               `            `                                  ` .HHMMHHHMMMHMMMMMHMNHMMMHWHHMgHHWHHH@MHHHHkHMH;``
                                                            `   .H@HMMM#HM@@MHHHHHMMMMHHHMmqkHbkHHMHMHH@MkHmHHMg.`
                                                             `  .HHHMMHMHHWMHpWHqHH@MM@KWMMWbHHqMkWUkHHMM@HMHHHg[
               `            `                                  ` N@MMH#MH0XXHHkWWHXWM@HHkXWHWWHHWWZyWHqMMMMH@NMH)
                                                            `    MHHM#MMWwtOwUmR0zOCvWHHMkXWXXSWWWRZUVHHM@MMMHHH:`
                                                             `  `WMMHH@MkwllOwH01?>;;<zOwWHZzVOOwwXv1OZWWMMMMH@H `
                                                               ``,MMHHHMH0O=zZI==>;;:::<<<1z11juAQkkmsOwwXMMMHmS.
               `            `                               `     HMMMMMSOz=1=z&zzz+++;;;;1zwXpWWUUUZOC1<zWMHN0O_`  `
                                                             `  ` WMM@HH0tOdkWkkHWWWXz+<;;1lOOwAgga&z+1<;+dHMKtl:``
                                                                ` (HM@HNZOUWU0Ov1zzzttOz<<=zwwIdH9wV0Z1?>>+dHWZ+~
               `            `                                      jHMHNZlztlwyWMH@OXkwI<<=OOOrtlz1+?>;>;><dk0z<`
                                                                   .XHMM0l=zwWUZOI=zOOwZz<1=?<<>>>><;;;;;><dKz+~ `
                                                                `   ztXMR=zl=zOllz<<+=tO<>????><;;;;:;;><><OC;!
                                                                 ` `.1ZHHz====<<><<?1=lz<:;<?=1<><<:::;;>?<v<!`  `
               `            `                                      `  <wWHz=??>;;;;>1Oz1<:::::<1>><;;;;<>??!
                                                                     ` (zdS==??>;;;+zO=lz<;+u&zz+?=zx<;????_  `
                                                                       ` 1zvzlz1+>+zlwUWWAwXwwOwXwwwwI;<??=!
               `            `                                       `  `  `.tOtOz=OwXXyXXOUVCCzIOOwwXC;+?=1` `
                                                                   ` `      jrrOz1XWWWXOOOv1v?<Id6zzrz+=??<`
                                                                          ` .OwtwzvUwVUSXz&+zzOtI?+zwz=1?==
                                                                          ` `.OrOXOOwzOrtlz++?=????zVO=?===_  `  `
               `            `                                                ` uwOXwkOtlOOwOZZI?<?+zwwzz==?+_`   `
                                                                         `   ``.wwwdWkO=l==z1=???>?1wuOI=??1_` `
                                                                          ```.K__TkXpywzzz=1zIz?11zww01????z_`(,``
               `            `                                             ` .MN/~~~7WHWkXwOwVwOltwvOOI??>??>   Mx   `
                                                            `  `           .###N/~~_?OUWWyXwwXwkUOv==>??>?j! ` (MNa, ` `
                                                            `` ````````` .d#HHH#N,~~~_<+zOVWkZXwO==?????11}     dM@@@HmJ...```````` ``
                                              `   `  `  `    ` ...  ` .&HHMMHHH##Hp_~_.~~<<<<?TXXOl=====zC     `(M@@@@g@g@H@mg....`      `  `
               `            `                  `  `` ```...(gMMMMMNadHHHMHHHHHHH#HHN,~.._...`._--?7zzzlzZ` `    .@@@@@gggggggggggHHHa..``  `
                                        `  `   `   ..(dqmgg@HHMB"YMHHMHHH@HH@HHHH##HMe......`.-___. ?OwC` .,.` ` W@@@@@gggggggggggg@gg@gm+, `  `` `
                                          ` `..(gW@ggggg@g@@#3(__~?MHH@HHHH@H@HHHHHHMHm_ . ..MN&-(+(-(C~ .MMMo. `(M@@@@@@gg@ggggmgmggggggg@gHa-.  ``
               `            `           ` ..MH@@@@@ggg@@@@#Y<>>_:~(M#HHHHHHHHHHHHHHHHHHN, `.MMMMNaga&J.+MMB11OX, .M@H@@@g@gggggggggmggg@gggggggmHHa., 
                   `
                                     `  `.M@H@@@@@@@@@g@@8<+<:::::<_TMMB"""TMMHHH@@HHH@MMx JvvM#MMHgMHHH#C~~_~<1I
                                         .W@@g@@ggg@@gg@ggggmgggggmmmmggggHH@h.
                                    ``` jM@H@@H@MHHHHM@@MI>??+<<::_<-_.~-__..`_?7WMH@HHHHM2~<_(ZMMH@HHMM%~_..~~_
                                        (?dM@gg@@@@@g@gg@gggggggggggggg@ggg@H@N ``
                                      `(@MH@@H@MMMM@Hg@@M<<<??zOVI<~~_.__<:_...~_~dHHH@@HHN, __<1TMHMgHM--_   _
                                          .~_dM@@ggg@@g@ggggggggmmgggg@ggggg@@M@@M)
               `            `        `.M@@@HMHHMM#MMMMMHD::;;<<1???++<<____(___:_(dHHHHH@@HN.  ..?OWHMHM/ .  ```~
                   (dM@@@ggg@@gggg@MMggggggggg@H@@g@@@@@@b
                                      (@HMgHMMMMMMMNHHM#<:;;;:;;;;;;<;::~:::<-.-_jHHH@H@@HHMb` .~~_(MMMNH,.   ` 
                                          _~dMM@@@@ggg@@@HMMMggggggg@@g@gg@g@@@@@M;`
                                     `dMHMMMNNNN#MMM#MMNc:;;;;;;;;<~::__((+?C+_-_WMHH@@@@H@MM;`_~~_JMHM#NHh.` ` ` 
                                         JM@g@g@gg@ggHMMM@ggggggggggggg@g@HM@@@N.
               `            `         HMHN#MM@@HHHHHHM#=(<>>>>>>;<+11+11<<:~~jaJ(M@@@@HH@@@HHb  ~~(M@HHMNNbH.` ` `
                   (M@@ggg@@gggggg@@@@@gg@gggg@ggg@@H@@@MM]
                                     .MMMHMHMMM@H@HHH3.0+>;<::~::::::::;<;:~~(HHH@MH@H@@@HHH@M-`_(HHHHHMM#Mkh     
                                         (M@@@gg@gg@gggg@gg@@gg@gggg@@g@g@H@@@@@N.
                                     `XMHHHMMMMMHkH#~d81z;;<:::::::::~~:__(((HHH@@@@H@@@H@@@HHb`.dMMHHHMMMMHH[`   
                                         ,M@@@g@ggg@g@g@gggggg@gg@gggggg@@H@@H@@ML `` ``
                                  `  ` MHMMHHbHWmH#`JHC?=z>>;<:::;:<<<<<<<<<:dH@@H@@@H@H@@H@H@N_.MHMq@MMHHMHqN.` 
                                      .,M@@@g@@gg@@@@@@@@gg@@@@g@gggg@HMM@@@H@@H;`
               `            `        ` MMHHkWHg@@HD`M$;+=z>>><<::::::::::::~(d@H@H@H@@H@@H@@@HM[JH@Hqg@HHHHgqM) ``
                   ,MMHg@ggg@ggggg@gg@gMMg@gg@gggg@MM@@@@@@@N.   `
                                 `` .JHgHMHHH@@@@MF`WI;:>+?<>;:~~:~~~~~_(J+gHH@@H@@HH@@@@@@@H@@Nd@MmqggqbbHHqHb` `
                                     ,M@@gggg@g@ggg@g@g@@@@@gg@g@@gg@MH@H@@@@@@b   `
                                   .MgH@MHH@@@@@@M% .k_:(<>+>?>;:~~_(dM@@HHMMHH@@@@@@@H@HH@H@H@HHHgqqmmqkbkqHgN.`
                                       .,M@@@gg@ggg@@ggggggHM@@ggg@@gg@M#H@@H@@@@@@[`
               `            ` `` .dMH@@MH@@@@@@@MMI_ (Xs++<;;::::_(+M@@@@@@HMM@H@H@@@H@@@H@@@H@@@HmqmqqkkkkqkHM;  
                   (MH@ggg@@gg@gggggggMM@@@gggg@@@MHH@@@@@@@@@N `
                               `.dMHMHHMM@@@@@@MMMZ<_  ~<?77T"^` (NNM@@@gggM@MMMH@HH@@@@@@@@@@HHHHkkqqqkkkqkkqM]  
                                   (M@@ggggggg@@ggg@g@H@@gg@@g@g@@MH@H@@H@@@@@M[ `
  `  `                          dHM@MHHM@@@@@@@gMHNz__ `  `_.` -jNNNM@@@ggggH@MM@@@@H@HHH@@@@H@@HNqHqkkqqkkqqqH@` 
      (MM@@gggg@g@ggg@ggMM@@@@g@@@ggHMH@@@H@@@@@@@N
  `   `                       `.MHM@HHM@H@@@@@@gMMNI<<___. ` _(dMNN#H@@@@@gg@@@MMHH@@@@@H@@H@@H@@MHkkqkkqqqqkqHM. 
      (#M@g@ggggggggggg@H@@@@g@g@@@@MMHH@@@@@@H@@gM[
               `              `,MHMMHH@@@H@g@@gHMM#Rz+++-___(zdNN#NMH@@@@g@gg@@@MM@H@@H@@HH@@H@HH@qqkkqkqkkkqqmM; 
                   (#@@gggggggggg@ggHM@g@g@gg@@@ggMMHH@@HH@@@@H@N
                              ` ZH@@HH@HH@@g@@HHM#HNwz=+>++wXHN###NMHM@@@@@@@g@@HMMH@@HH@@@@H@@@@HHkqqqqkqqqqHmM[ 
                                  (MM@gggg@gggg@g@gH@M@@@@@@@@@@gMHH@HH@@@@@@gMM-`
  `                            ` 4M@HH@H@@@HWHHHMNHMI1OwwXUUXM##H##MHHH@@@@@g@g@@@MMH@@@H@H@@@@@@@MqqqqqqHkqqqmHL`
      (M@@@g@gggggggg@MMM@@@@@@@@@@@gMHH@@H@@@@H@HHH]  `
               `            `     4MH@Hg@@HHgHHMMMHM$(dWQQmgMNN#H#HHHHH@@@@@g@@@MMMMM@H@@H@H@@@@H@Mqqqqqqqqqqqqgb
                   -.MM@ggg@gg@@@@@@@@@g@@@@@@@@@g@MHHH@@HHM@@@@gMb `
                                   WMHHHHHggkQHHMM@HHZXM#N##N###HMMHHHHH@@@@@g@@@@@MHH@H@H@@@@@@H@@qqqmmmqqkqqqHN_
                                       .HHg@gggg@gggg@@@gg@g@@@@@@@@@gM#H@HH@H@@@@@@HN
                                   .M@HMqHgHHmggmHHMMHMHM#NN##M@MM##HHHHH@@@@@g@g@@@M#HM@@H@@@@@@H@mqmgHmqqkqmmHM
                                       :.dMM@@@g@g@gggHMg@@@@@gg@@@@@ggM#H@@HH@HH@@@@@M-`
                                  `  7HMHqgmkqqqmmkpHMM@@HHMMMM#####HHHHHH@@@@@@@@@@@HHM@@@@@@@@@@HHqqgHmqqqqmqHMI_dM@@g@ggggggg@@@@@@@@@g@@g@@@@M#HH
                                      @@HM@@@@@@@M] `
               `            `        ``?WgmmmqqqmqqqkbkbbbWHMNN####HHHHHH@@@@@@@@@@@@@MMM@@ggH@@@@MMqmmmqqkqqmqHM$
                   <dM@@g@g@@gggH@@@@@g@@@@@@g@@@g@#HHHH@HH@H@@@@@]
    ` `                                 ` ?THmHmqqkqkkbWHHMHM#NH####HHHHH@H@@@@@@@@@@@@MMHMgg@@@@@@MmmmmqqqkmgqqMD
        :JM@@@ggggggg@@@@@@@@@@@@@@@@@@@#M@HH@HHH@@H@@H[`
                                           `   `~!!!OHHHM#HMN##HH#HHHHHHHH@H@@M@@@g@@@@@@MMMgg@@@@HMmggmqqkqmgmmMb
                                               <JMM@g@gggggMM@@g@@@g@@@@@@@@@@gMHH@@HH@H@@@H@@b`
               `                                    .MHMN#H#NHMHHH###HHHHHH@@@@@@@@g@@@@@@MMMHgg@@@HgmmmqqkqmgmqMb
                   >j#H@@gggg@HH@@@g@g@@@@@@@@@@@@gMHHH@H@@@H@@@@@M-`
   `  `                     `                     ` `(MNNMMM##MH#HH#H#HHH@HH@HH@@@gg@@@@@@gHMMM@@@@MHggmqkkqqggqM#
       ++MM@@ggggHMHM@gg@g@@@@@@@@@@@@gMHHH@HHHHH@@H@@HL
                                                       TMMM#MHMHH##HHHHHHH@@@@@@@@@@g@g@@@@@M#NM@@@HHg@gqkkqkmmHHN
                                                           >>MH@gggggMHMM@@gg@@@@@@@@@@@@g@MHHH@H@HHHH@@@@@N. `
                                                      ` .MMMHHMH#H#H#HHHHH@H@@@@@@@@@g@g@gg@@MNNM@@@M@ggqqqkqqqqHN
                                                          >;dHM@gggM#HH@@@g@g@g@@@@@@@@ggHM#HH@HHH@H@@@@H@M[
  `  `         `                                         dMHMMMHH###H#HHHHH@@@H@@@@ggg@@g@@@@H#NNM@H@ggHkqqqqkqmHMz
      ;dMH@ggMHHH@@@@@@@@@@g@@@@@@@@gM#HHHHH@@HH@@@@HM@
                            `                            .MHHMMHHH#H###HHH@H@H@@@@@@@@@@@@@@@M###NM@@@gqqkkqqqmHgMv
                                >JMH@gM#HHH@H@@@@g@ggg@@@@@@@@@M#HHH@H@HH@@@@@@@M- `
                                                          (MMMMHHH#HHHHHHHH@@H@@@@@@g@@@@@@@@M###NNMHggmqkkkqggmHMI
                                                              >JMMHMMHHH@@@@@@@gg@@@@@@@@@@@gHNHHHH@H@@H@@H@@@@p `
               `                                         ` (MM@HHH#HHH#HHHHH@@@@@@@@@@@@@@H@HMHH###NMMgmqkkkHggqHMP
                   >+MHHMHHH@H@@@@@@@Hg@@@g@@@@@ggHN#HH@HHHHM@@@@@@@b  `
                            `                            `` .MM@HHHH#HHHHHH@@H@@@@@@@@@@@H@@HMHHHHH#NMgmqqkqmgmmHMb
                                ><MMHH@H@H@H@@@@g@@@g@@H@@@@@g@@##HHHHHHHHHH@@@@@N
                                                             JHHHH#HH#HHHHHMH@@H@@@@@@@@@@@@@MHH#H##NHgqkbkqH@mqHMb
                                                                 >1dMH@HHH@@@H@H@@g@ggg@g@@@g@@gg##HHHHHHHHH@H@HH@H[`
                                                            `.MHHHMHHH#HHH@H@@@@@@@@@@@HH@H@@MH#MMMM#MgqkkkqmmgmmM#
                                                                <>dHMH@HHMHH@@H@@@@@@@g@g@@@@gg@##HMHHHMM@@@@@@@@HN.`
               `                                             .HHHHHH#HHHHM@@@H@@@@H@@@@@@H@@@HMMWkkHMMmkkkkqggmmmM#
                   ??dMHH@@@@HH@H@@@@@g@@@ggg@@@@ggMN#HMH@@@@HHH@@@@@M]
                            `                                .@HHHHHHHHHHHH@H@@@H@@@H@H@@@H@H@MNHkWMM@qkkkqqm@mqmHN
                                ??dH@H@HH@@@H@@H@@@@@@@@g@@@@@gH####HHMMM@gg@@@@@@M]
                                                            `J@HHHHHHHHHH@@@@@@H@@@H@@@@H@@H@@HMHHMMMmkkqqqmmgmqmHHz
                                                                +dMH@@@H@H@@H@@@@@@@@g@@@g@@@ggNN#NNNN##MMHg@@@@@@]`
               `                                         `   d@HHHHHHHHHHH@H@H@@@@@@@@H@@@@H@@@H@HHMmqqkkkqqggmqmHMI
                   =dHMH@H@@@HHH@@H@@@@g@@gg@g@@g@NNN#NN#####M@@@@@@@b
                            `                               .H@@HHHHHHHHH@H@@@@H@@H@@H@@H@H@@H@@@HHHqqqqkkqkggqqqHMr
                                +zMMH@H@@@@@HH@@@@@@@@@@@@ggggHNNNN######HM@H@@H@@N
                                                         ` `.M@HH@H@HHH@H@@H@@@@@H@@@@H@@H@@@@@HH@MqqqkkkkqmHmqqmgMP
                                                             <1WH@H@@@H@@@H@@@@@@@@@@@@g@@gHNNNN##H#HHHH@@H@@HHH[` `
                                                         `  (@@H@@HH@H@HH@H@@@@@@@@@@@@@@@@H@@@@HHMkkqkkkmqmgmqqqmMb
                                                             (1dMH@@@@@HH@HH@@@@@@@@@@@@gggMNNN#HMH@@HHHH@@H@@H@N, `
               `                                          ` W@@@@HHHHHHH@H@@@H@H@@@@@H@@@@H@@@H@@MHkqkkkkqqmgmqkqgH#
                   (1vM@@H@@@@@H@@H@@@@@@@@gg@gggMN##HHHHMHHHHHHM@@@@HHN`
                            `                            ` .M@@@H@@HH@H@MH@@H@@@@@H@@@@@@H@@H@@@#dHqkkkkkHggmqqkqq@N~
                                <=W@@@@@@@H@HH@H@@@@g@@@@g@@gMN##HHHHHHHHHHMH@@@@@HM|`  `
                                                           J@@@@H@@H@H@H@@H@H@@H@@@@@@@@@@@@@@HM%JHkkkkkqmgqqkkqqqHM
                                                               <(+dMHH@@@H@HH@H@@@@g@gg@@@gggMNN#MMMMMHHHHH@HHHHH@H@b`
               `                                         `.H@@@@HH@@HH@H@@@@@H@@@@@@@@H@@@MHHHM# JHqqkkkHmmqkqqkqmgM;_
                   <zMHHH@H@MHH@HH@H@@@g@ggg@ggMNNNNMM@ggM@HHHHHHHM@@@M_
                            `                         `  `(@@@@H@HH@@@H@H@@@H@@@@@@H@@@@@@HMMWH].(NqkkkbqqqkqkqkqmgMr~
                                (+dH@@@@@M@@HHHH@H@@@@g@gg@@@MNNNN##MMMH@g@MM@g@@@HF`  `
                                                         .MH@@@@@@@HH@@H@H@@@@@@@@@@@@@@@@MMHMH%.(MqkkkbqqqqqkkqmmHH]~
                                                             (<dMM@@@H@@H@@@@H@@H@g@@@@gM@@MNN######HHHMHMH@g@@M``
                                                     `` `.MH@@H@H@@H@H@@@@@@H@@H@@@@@@@@@@MHMMD._(MqkkbpkkkkkqkHqqqm@_
                                                         :;1M@@@@@@@@@@@@@@@@@@@g@ggM@gM#N###HH#HHHH##H@@@@M<
               `                                       `.HH@@@M@H@H@H@H@@H@@@@@@@@H@@@@@@@@@HMl
                   --(NqkbbpppppbkkqqqqmHqMMMMH@@@@@H@@H@HH@H@@@@g@@HHMH@MNN##HH####HM@@@@@HHb`  `
                            `                         ` 
                                JM@H@@@@@H@@@@@H@@H@@@@@@@@@@@@@@@@@@MN#MHNbkbbbbbbkkkkqqkkHHHNNNNM@@@@H@@H@@H@@H@@@@@ggMHMMMMMMMHHHMMMM@@@@@H@HHN_
                                                      `
                                                          .WHH@MM@@@H@H@@@@H@@H@@H@M@H@@@@@@@@@@MNNN#NbkHkHkqqqqqqqqqqgHHMNNNM@@H@@@HH@HHH@H@@@g@g@MH
                                                          Mg@gMMMMMNNN#N###HHH@@HHr
               `                                       
                   .@H@@@@@@@@H@HH@@H@@@@@@@HH@H@@@@@@@@MNNN#MNHbbpkkqkqmqkqHqHMM@MNNNNM@@@@H@@H@@HH@@@@@@@@MHM@ggMMNMMHHMMMM##HHHHHHMN
                            `                       `  
                                dMH@M@@@@H@H@@@@H@@@@@@@@@@@@@@@@@@@@MNNNMMMMMHkbbHWkbkkHHHMHMHWMMMNNMM@@@@@HH@@@HHH@@@@gMHM@ggHHgMMMMHgg@@@@MH##HM# 
                                  `
                                                     `
                                                         .@HHH@@@@M@H@@@H@@@@@@@H@@H@@@@@H@@@@@NM#HNNNNHHNUHbHpbkqHNNMNN#N#N#NNM@@@@@HHHHHHHH@@@@g@MM
                                                         @@gmMMMHggMMMHMH@@HH@@MM%
                                                  `   
                                                      JMH@@@@@@@H@HH@@H@H@@H@@@@@H@H@H@@@@@MN#HHHHHHHHMNMNWpbHM#NHHHH#H####NNM@@@@M@HH@H@HH@@@@H#H@@@
                                                      @MNNMMgggMHHHM@@HH@MF`
               `                                     
                   .H@H@@@@@@@@@@HH@@H@@@@@@@@@@@@@@H@@@@N#H#HHHHHHHHHH##NNM#HMHHHHHHHHH##NNM@@@@@@H@HH@H@@@HH#HH@@@HMN#HMHggMMMM@@MHH#
                            `                     `` 
                                .@HH@@@@@@@HH@@@@@@@@@@@@@H@@@@HMMMM@M##HHHHHHHHHHHHHHHMHHH#H@@H@H@HHH##NM@@HMH@HHH@H@H@@@M#HHHHH@M@@@H@@ggmM@MMHMM\ 
                                `
                                                   ` 
                                                       dMM@@@@@@@@H@H@@@H@@@@@@@@@@@@H@MWkHqM##HHHHHHHH@H@H@HHHH@HMH@@HHH@HHHH#NNM@@@@HHHHH@H@H@@M#HH
                                                       MHHHHHH@H@@@@ggH@HMHF
               `                                    
                   .HMHH@H@@g@@HH@H@H@@@@@@@@@@@@@@MNHHWW##HHHHHHHHH@HH@H@@HHHHHM@@H@HH@HHHH#NNM@H@@H@MHHHHHH@MHHHHHHHHH@HH@@H@@@ggMM@
                            `                 `   ``
                                (@@@@H@@@@@@@@@@@@H@@@@@@@@@@@@@@MMMM###HHHHHHHHHH@H@H@H@HH@MM@HHH@H@@HHHH##NM@HH@HMH@@H@@@@@@MMHMHHHHHHHH@H@@Hg@M[`
                                                    
                                                        W@HH@@@@g@@HHHH@HH@@@@@@@H@@@@@@@@@@M##HHHHH@HHHHHH@HH@HH@HHHM@@@H@HH@@HHHH##MM@H@HH@HH@HHH@@
                                                        @ggMMMMHH@@M@H@@@@H@M\
                                               `   
                                                   .M@HH@@@@@@@@@@@H@@H@@H@@@@@@@@@@@@@@HH#HHHHHHHHH@H@H@@H@H@HHHMH@H@HH@HHHHHHH#N#M@H@@@H@H@@@@@@@@g
                                                   ggg@@@@@g@@@@@@@M;
               `                                  
                   `JH@@H@@@@@H@H@@@H@@@@@@@@@@@@g@gg@@gMH##HHHH@HHHHHHHHHH@@@H@HMM@@HH@@HHH@H@HHH##MM@@H@@H@@@H@@@@@@@@gggggg@gg@@@@@HN.
                            `                     
                                `dMHH@H@@@@@H@H@H@@H@@@@@@@@@@g@@@@gH##HHHHH@H@HHHH@@HH@@@HH@@HMH@@H@HH@HH@HHHHH##NMH@HH@H@H@H@@H@@@@@@@@ggggg@@@@H@H
                                L``
                                                   
                                                       H@@H@@@@@@@@H@@H@@@H@H@@@@@@@@@@@@MMH#HHHHHHHHHHHHHH@HHH@@HH@H#H@H@HHH@@HHHHHHHH###M@@H@@H@@@@
                                                       H@@@H@@@@@@@@@@@@@@@@MN  `
               `                                  
                   .@@H@@@@gg@@H@@H@H@@@@@@H@@H@@@@@@@MNHHH#HHH@@HHHHHHHH@HH@@@HMH#M@@H@@HHH@H@HHHHHHH#NMH@@H@@@@@H@@H@@@H@@@@@@@@@@H@MMN_
                            `                 ` ` 
                                (MMH@H@@@@@@@HHH@@H@@H@@@@@@@@@@@@MNNHHHHHHHH@@HHHHHH@H@@HH@@@H#M@@@H@@HHHH@@HH@HHHHMNMM@@H@@@H@@@@@@@@@@@@@@@@@@H@@H
                                # `
                                               `  
                                                   d@@@@@@@@@@@@H@@H@@H@@@@H@@@@@@@@HM#NMHHH@H@@HHHHHHH@HHH@HH@@@HMM@@@HH@H@H@HHH@HHHHHHH#NM@@H@@@H@H
                                                   @H@@@H@@H@@H@MH@H@H%  `
                                                ` 
                                                    H@@HH@@@@@@HH@H@@HH@H@H@@@@@@@@@@M#NNMH@HHHMH@HHHHHHH@H@H@HH@@@MM@@H@HH@HH@H@HH@@HHHHH#MNM@HH@@@H
                                                    @@@H@@@H@@@@H@@@@HH#
               `                               ` 
                   .M@@H@@@@@@@@H@@H@H@H@H@H@@@@@@@gM##NNMMHHHH@HHH@HHHHH@H@H@@H@@@HMH@@@@H@@HH@@@HMH@@HHHHH##MMHHH@@@@H@H@@@@@H@@H@@H@M'
                            `                  ` 
                                J@@@@@@@@@@@@HH@H@@@@H@@@@H@@@@@MM###NM@H@H@@H@H@HHH@HH@H@HHH@H@@#@@@HHHH@HH@H@HHHH@H@HHHHHH#MH@HHHH@@@H@H@@@H@@H@HHF
                                               ` 
                                                   d@@@H@@@@@@H@@@H@H@H@@@@@@@@@@@@M##H##N@HH@HH@HHHHHH@HH@HH@HH@H@@HHH@@H@H@@@HHH@H@HH@H@@HHHHHHMM@H
                                                   @H@@H@@H@H@H@@@HM#``
               `                                
                   .@@@H@@@@@@@@HH@@H@H@H@@H@@@@@@@M#H###NNH@HHH@HHHHHHHH@H@@H@@@H@H@M@@H@HH@HHH@@HH@H@@HHHH@@HHHHHMNM@HH@HHH@@H@@HH@HM'` `
                            `              `   
                                `jM@@@@@@@@@@H@@HH@H@H@HH@@H@@H@M###H#H#NMH@@H@@MH@H@@HHHH@HHHH@@@HM@@@@MHH@HH@@@@HHH@@H@@MH@HHHHHMNNM@HH@@HH@@@H@@M%
                                            `  
                                                .H@@@@@@@@@@@H@@H@HHM@H@@@@@@@@M#HHHH####M@HH@H@@HHHHMMHHHHHHH@HH@@MHH@@HH@H@@HHH@@H@@HHHHHH@HH@@@@HH
                                                HMM@H@@@HH@H@HF   `
                                               
                                                   ,M@@@@@@H@@@@@HH@H@@H@@H@@H@@@M##HHH#HH#MM@HH@HH@HH@HHMHH@HH@@H@@H@MH@@H@@H@HH@H@HH@HH@@H@@HH@H@HH
                                                   @H@HHHMM@@H@@@H@#     `
               `                                
                   W@@@@@@@@@@HH@H@H@H@H@@H@@H@MNHHHH#HHHHNMH@@H@H@HHHHHHHHHH@HH@HH@@#@@@H@@HH@H@H@@@H@H@@H@H@H@@H@HH@@@H@HHHM@H@H@M\`
                            `                  `
                                .M@@@@H@M@@H@H@H@MH@HH@@@@@M##H##H#HHH###H@@HH@HMHHHHHHHHHH@H@@@H@MH@H@@@@@H@@@H@@H@@HH@HHH@HH@H@@HHH@HMHHHHH@MM@
                                                `
                                                    .M@@@HH@M@@H@@H@@@H@H@H@@M####HHH#HH#H##@HH@H@@HHHHHHHHHHHH@H@@@HMHH@@H@@@HHH@H@H@@@@H@@H@@H@H@H@
                                                    H@H@HH@HHH@H@D
               `                               `  
                   ?MMH@@@@H@HMH@HHH@H@@@MM##H#HHMHHHHHHHHH@@H@H@HHHH@HHHHHH@M@HH@@HH@@@@HH@H@H@@H@HH@H@HH@HH@@@HH@H@H@@@@H@@@@MD
                            `                  `  `
                                ?MH@@H@@H@@@H@@HH@H@HM###H#HHHHHHHHH##H@H@H@H@HHH@HHHHHHH@@@H@@HH@H@H@@H@@@HH@HH@HHHH@H@HH@H@@H@H@HHHH@@@@@HF
                                                   `
                                                       .TM@@H@H@H@HH@@@H@MM##HHH#HHHHHMHHHHHM@@@@H@HHHHHHH#HH@@H@@@@@HM@@HH@HH@HH@HH@HHM@@@H@@@H@@HH@
                                                       @H@@HH@H@H@@@]
                                                      
                                                          .UHHH@H@H@@HHH@H#HH#HHH#HHHHHHHHH#HHH@HH@H@HHHHHHHHHHHMH@@H@H#M@@HH@@@H@HMH@H@HH@@H@HH@@H@H
                                                          @HH@HH@HH@@@@@]`
               `                                      ``
                   .TMHH@@H@@H@MHH#HH#HH#HHHHHHHHHHHHH@H@H@HHHHHHHHHHH@@MH@@@HNH@H@@HH@@@@M@H@@@H@@@H@@H@HHHH@HH@H@@@H@@@H]
               */
#include<bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define rep(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
#define _GLIBCXX_DEBUG
using ll = long long;
using ui = uint64_t;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
using pll = pair<ll, ll>;
const ll INF = 1LL << 60;
const ll inf = 1LL << 50;
const long long mod = 998244353;
using mint = modint998244353;
vector<int> di{1, 0, -1, 0};
vector<int> dj{0, 1, 0, -1};
struct Edge {
  ll from;
  ll to;
  //ll co;
};
ll op (ll a, ll b){return a+b;}
ll mapping(ll f, ll x){return max(f, x);};
ll composition(ll f, ll g){return max(f, g);};
ll id(){return 0;};
ll e(){return 0;};
const ulong MASK30 = (1UL << 30) - 1;
const ulong MASK31 = (1UL << 31) - 1;
const ulong MOD = (1UL << 61) - 1;
const ulong MASK61 = MOD;
const ulong base = 1000000007;
//mod 2^61-1を計算する関数
ulong CalcMod(ulong x)
{
    ulong xu = x >> 61;
    ulong xd = x & MASK61;
    ulong res = xu + xd;
    if (res >= MOD) res -= MOD;
    return res;
}
//a*b mod 2^61-1を返す関数(最後にModを取る)
ulong Mul(ulong a, ulong b)
{
    if(a == 0 || b == 0)return 0;
    ulong au = a >> 31;
    ulong ad = a & MASK31;
    ulong bu = b >> 31;
    ulong bd = b & MASK31;
    ulong mid = ad * bu + au * bd;
    ulong midu = mid >> 30;
    ulong midd = mid & MASK30;
    return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
int main() {
    int M;
    string S;
    cin >> S >> M;
    vector<ulong> pow(100001);
    pow[0] = 1;
    rep(i, 100000){
      pow[i+1] = Mul(pow[i], base);
    }
    ll res = 0;
    rep(k, M){
      string T;
      cin >> T;
      ulong hashs = 0;
      ulong hashr = 0;
      rep(i, T.size()){
         hashs = Mul(hashs, base) + (S[i] - 'A' + 1);
      }
      rep(i, T.size()){
        hashr = Mul(hashr, base) + (T[i] - 'A' + 1);
      }
      for(int i = T.size(); i <= S.size(); i++){
        if(hashs == hashr)res++;
        hashs = CalcMod(hashs + MOD - Mul(pow[T.size()-1], (S[i-T.size()] - 'A' + 1)));
        hashs = Mul(hashs, base);
        hashs = CalcMod(hashs + (S[i] - 'A' + 1));
      }
    }
    cout << res << endl;
} 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0