#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i,n) for(int i = 0; n > i; i++) #define MODU 33 #define Range(x,a,b) ((a) <= (x) && (x) <= (b)) #define POWT(x) ((x)*(x)) #define ALL(x) (x).begin(), (x).end() #define C_D(c) ((c) - '0') #define D_C(d) ((d) + '0') using namespace std; typedef vector Ivec; typedef pair pii; typedef long long int ll; /*! * @brief KMP法テーブルを作成する * @param[in] pattern 検索文字列 * @return テーブルのポインタ。失敗したらNULLを返す。 */ vector kmp_table_init(const char *pattern) { vector table; int i, j; /* パターンの文字参照点 */ int ptn_len = strlen(pattern); /* パターンの文字列長 */ /* KMPテーブルの領域を確保する */ table = vector(ptn_len + 1); /* テーブルの値を設定する */ table[0] = 0; for (i = 1, j = 0; i < ptn_len; i++) { if (pattern[i] != pattern[j]) { table[i] = 0; j = 0; } else { table[i] = ++j; } } table[ptn_len] = 0; //for (i = 0; i < ptn_len; i++) printf("[kmp]:table[%d]=%d\n", i, table[i]); return table; } /*! * @brief 文字列を探索する * @param[in] text 検索対象文字列 * @param[in] pattern 検索文字列 * @return 発見位置のポインタを返す。失敗したらNULLを返す。 */ char * kmp_search(const char *text, const char *pattern) { vector table; int i = 0; int j = 0; /* ずらし表を作成する */ table = kmp_table_init(pattern); /* 比較処理 */ while ((text[i] != '\0') && (pattern[j] != '\0')) { /* 文字の比較 */ if (text[i] == pattern[j]) { i++; /* テキストの位置を1文字進める */ j++; /* パターンの位置を1文字進める */ } else if (j == 0) { i++; /* テキストの位置を1文字進める */ } else { j = table[j - 1]; /* ずらし表を参照して進める */ } } if (pattern[j] != 0) return(NULL); return((char *) text + (i - j)); } int main() { char str [500001]; int m; scanf("%s", str); scanf("%d", &m); ll cou = 0; REP(i, m) { char pat[101]; scanf("%s", pat); char *pt = str; while (1) { char *ret = kmp_search(pt, pat); if (ret == NULL) break; pt = ret + 1; cou++; } } printf("%lld\n",cou); return 0; }