Problem: G： 検閲により置換 (Censored String)

Problem Statement

You are given the string S, and the set of strings \mathcal P whose size is N. Now we consider applying the following operation to S:

* Choose exactly one character in S, and replace it with '*'.



Let s_i be a i-th character of S, S_{ij} be a consecutive substring in S such that  S = s_i s_{i+1} $\cdots$  s_j, and p_k as the k-th string of P. Your task is to calculate the minimum number of operations for satisfying the following condition.

* For all pairs (S_{ij}, p_k), it is satisfied that S_{ij} \neq p_k.



Input

An input is given in the following format.


S
N
p_1
p_2
$\vdots$
p_N


* In line 1, you are given the string S.
* In line 2, given an integer N. N means the size of P.
* From line 3 to the end, given p_i, the i-th string of P.



Constraints

* 1 \leq |S| \leq 10^5
* 1 \leq N \leq 10^5
* 1 \leq |p_1| + |p_2| +  $\cdots$  + |p_N| \leq 10^5
* If i \neq j, it is guaranteed that p_i \neq p_j
* S, and p_i include lowercase letters only



Output

Print the minimum number of operations in one line.

Sample Input 1


brainfuck
1
fuck


Sample Output 1


1

For example, if you change "brainfuck" into "brainf*ck", you can satisfy the condition. You have to perform operation at least once, and it is the minimum value.

Sample Input 2


aaa
1
a


Sample Output 2


3

You have to operate for all characters.

Sample Input 3


hellshakeyano
3
hell
shake
key


Sample Output 3


2

In this case, for example, if you change "hellshakeyano" into "h*llsha*eyano", you can satisfy the condition. Notice if you replace one character, it might happen that several strings in the set P, which appear as the consecutive substring of S, simultaneously disappear.





Example

Input

brainfuck
1
fuck


Output

1

Solution (in CPP):

Solution:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


class AhoCorasick {

  struct Node {
    std::map<char,Node> child; //遷移辺(!)
    std::vector<size_t> pattern; //マッチするパターン(のindex)
    Node* failure; //遷移失敗時の遷移先ノード
    Node():failure(NULL){}
  };
  Node root; //根

  //PMAのクリア
  void clear_graph(){
    root.child.clear();
    root.pattern.clear();
  }

  //Trieを構築
  void generate_trie(const std::vector<std::string>& patterns){
    size_t n = patterns.size();

    for(size_t i=0; i<n; i++){
      Node* t = &root;
      for(size_t j=0; j<patterns[i].length(); j++){
        t = &(t->child[patterns[i][j]]);
      }
      t->pattern.push_back(i);
    }
  }

  //failure辺を追加
  void add_failure_edge(){
    std::queue<Node*> que;
    que.push(&root);

    //幅優先探索で帰納的に失敗時の遷移辺を追加していく
    while(!que.empty()){
      Node* t = que.front(); que.pop();
      std::map<char,Node>::iterator itr = t->child.begin();

      for(; itr != t->child.end(); ++itr){
        que.push(&(itr->second));
        char c = itr->first;
        Node* node = &(itr->second); //文字cで遷移する頂点

        Node* anode = t->failure; //失敗したときの遷移先
        while(anode != NULL && anode->child.count(c)==0) anode = anode->failure;

        //遷移失敗時に続けられる別の頂点へ遷移
        if(anode == NULL){
          node->failure = &root;
        }else{
          node->failure = &(anode->child[c]);
        }

        //マッチするパターンを追加
        for(size_t i=0; i<node->failure->pattern.size(); i++){
          node->pattern.push_back(node->failure->pattern[i]);
        }
        //メモリ食いすぎ回避のため切り詰めておく
        std::vector<size_t>(node->pattern).swap(node->pattern);

		          std::vector<size_t> buf;
          std::sort(node->pattern.begin(), node->pattern.end()); //いらないかも
          std::sort(node->failure->pattern.begin(), node->failure->pattern.end()); //いらないかも
          std::set_union(node->pattern.begin(), node->pattern.end(),
                         node->failure->pattern.begin(), node->failure->pattern.end(),
                         std::back_inserter(buf));
          node->pattern = buf;

		  
        /* 2016/2/28追記:
          上記のように1つずつpush_back()していくと、メモリを無駄に使ってしまうかもしれません。

          試しに、パターンpat={a,aa,aaa,aaaa,aaaaa,...,(aが10000個)}のような入力を想定すると、
          1つずつpush_back()だと、node->patternのcapacity()は16384のものが並んでしまいますが、
          速度よりもメモリが問題になる場合は、速度を犠牲に切り詰めて保持するとよさそうです。(#include <algorithm>が必要)

          //swap技法とか
          std::vector<size_t>(node->pattern).swap(node->pattern);

          //set_unionするとか
          std::vector<size_t> buf;
          std::sort(node->pattern.begin(), node->pattern.end()); //いらないかも
          std::sort(node->failure->pattern.begin(), node->failure->pattern.end()); //いらないかも
          std::set_union(node->pattern.begin(), node->pattern.end(),
                         node->failure->pattern.begin(), node->failure->pattern.end(),
                         std::back_inserter(buf));
          node->pattern = buf;

          //copyとか
          std::vector<size_t> buf;
          std::copy(node->pattern.begin(), node->pattern.end(), std::back_inserter(buf));
          std::copy(node->failure->pattern.begin(), node->failure->pattern.end(), std::back_inserter(buf));
          node->pattern = buf;

          //そもそもvectorじゃなくてlistなどを使った方がよいか

         //capacity()で確保メモリサイズを確認
         std::cout << node->pattern.capacity() << std::endl;
        */
      }
    }
  }

  //Pattern Match Automatonを構築
  void make_PMA(const std::vector<std::string>& patterns){
    clear_graph();
    //trieを構築
    generate_trie(patterns);
    //failure辺を追加
    add_failure_edge();
  }
  
public:
  AhoCorasick(const std::vector<std::string>& patterns){
    make_PMA(patterns);
  }

  //文字列の探索
  std::vector< std::pair<size_t,size_t> > find(const std::string& text){
    std::vector< std::pair<size_t,size_t> > ret;
    Node* node = &root;
    
    //PMAにtextを入力
    for(size_t i=0; i<text.length(); i++){

      //遷移失敗するかどうか確認
      while(node != NULL && node->child.count(text[i])==0) node = node->failure;

      //次の頂点へ移動
      if(node == NULL) node = &root;
      else node = &(node->child[text[i]]);

      //もしパターンが見つかったら保存
      for(size_t j=0; j<node->pattern.size(); j++){
        size_t e = i; //見つかった位置(パターンの文字列の最後の部分)
        size_t pi = node->pattern[j]; //見つかったパターンのindex
        ret.push_back(std::make_pair(e,pi));
      }
    }
    return ret;
  }
};

typedef pair<size_t,size_t> pst;
typedef pair<int,int> pint;

vector<string> pat;

string S;
int N;

bool cmp(pst a, pst b) {
  return a.first < b.first;
}

bool cmp(pint a, pint b) {
  return a.second < b.second;
}

int main(){
  while (cin >> S >> N) {
	set<string> se;
	pat.clear();
	for (int i = 0; i < N; ++i) {
	  string tmp;
	  cin >> tmp;
	  se.insert(tmp);
	}
	for (set<string>::iterator it = se.begin(); it != se.end(); ++it) {
	  if (pat.empty()) pat.push_back(*it);
	  else {
		string prev = pat.back();
		if ((*it).substr(0, prev.size()) == prev) continue;
		pat.push_back(*it);
	  }
	}
	//COUT(pat);
	
	AhoCorasick ac(pat);
	vector<pst> ret = ac.find(S);
	/*
	vector<pint> inters;
	for (int i = 0; i < ret.size(); ++i) {
	  int e = ret[i].first;
	  int pi = ret[i].second;
	  int f = e + 1 - (int)pat[pi].size();
	  inters.push_back(pint(f, e+1));
	}
	*/
	
	int res = 0;
	sort(ret.begin(), ret.end());

	//COUT(ret);
	//sort(inters.begin(), inters.end(), cmp);

	//COUT(inters);
	int goal = -1;
	for (int i = 0; i < ret.size(); ++i) {
	  int e = (int)ret[i].first + 1;
	  if ((int)goal <= (int)e - (int)pat[ret[i].second].size()) {
		++res;
		goal = e;
	  }
	}
	
	/*
	for (int i = 0; i < inters.size(); ++i) {
	  int e = 
	  
	  if (goal <= inters[i].first) {
		++res;
		goal = inters[i].second;
	  }
	}
	*/

	cout << res << endl;
  }

  /*
  //探したいパターン
  std::vector<std::string> pat;
  pat.push_back("ab");
  pat.push_back("bcd");
  
  AhoCorasick ac(pat);

  //入力文
  std::string text = "abcde";

  //テキストの探索
  std::vector< std::pair<size_t,size_t> > ret = ac.find(text);

  //結果の出力
  for(size_t i=0; i<ret.size(); i++){
    size_t e = ret[i].first; //マッチパターンの文字列最後の位置
    size_t pi = ret[i].second; //マッチしたパターンのindex
    size_t s = e + 1 - pat[pi].length(); //マッチパターンの文字列最初の位置

    std::cout << "[" << pat[pi] << "] find at index " << s << std::endl;
  }
  */

  return 0;
}