#include using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x))%modulo) #define Inf 10000000000000000 struct KMP{ string S; vector A; KMP(string s){ S = s; A.resize(S.size()+1,-1); int x = -1; for(int i=0;i=0){ if(S[i]==S[x])break; x=A[x]; } x++; if(i!=S.size()-1){ if(S[i+1] == S[x]) { A[i+1] = A[x]; continue; } } A[i+1] = x; } } //文字列[0,pos]の接尾辞と接頭辞が何文字一致しているか int get_length(int pos){ return A[pos+1]; } }; int main(){ string S; int M; cin>>S>>M; int ans = 0; for(int i=0;i>c; KMP K((c + " " + S)); for(int j=0;j