ACdream 1727 Sequence

Description

Losanto has a sequence {a[1],a[2],…,a[n]} with 

n positive integers. Superman has some positive integer sequences with different size. Losanto wants to know the total occurrences of every sequence Superman has in Losanto's sequence (the occurrences are allowed to overlap). 

We say one sequence B occurs in another sequence A if there is a contiguous subsequence of A that is the same as B after add an integer.

For example A={1,2,3,5},B={2,3} then B occurs two times in A. The occurrences are {1,2}and{2,3} . And the addition is -1 and 0.

Input

There are multiple test cases. (No more than 20 cases) 

For each test case:The first line contains two integer n and m ( 

1≤n,m≤10000), indicating the size of Losanto's sequence and the number of sequences Superman has. In the next line, there are integers, a[1],a[2],…,a[n], indicating Losanto's sequence. In the following m lines, each starts with an integer k[i]( 

1≤k[i]≤10000) - the size of the sequence. Then k[i] space-separated positive integers follow, indicating the sequence. 

The total sum of k[i] is less than or equal to 100000. Other integers are between 1 and 10000, inclusive.

Output

For each case, One line with a number indicate that the sum of occurs times.

Sample Input

4 2

1 2 3 5

2 2 3

2 2 4

Sample Output

3

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
const int maxn = 100105;
int n, m, a[maxn], x, y, c[maxn];
long long tot;

struct ac_machine
{
  map<int, int> Map[maxn];
  std::map<int, int>::iterator it;
  int fail[maxn], cnt[maxn], root, to;
  void clear()
  {
    to = 0; root = 0;
    Map[0].clear();
    memset(fail, 0, sizeof(fail));
    memset(cnt, 0, sizeof(cnt));
  }
  void insert(int x)
  {
    int now = root;
    for (int i = 1; i < x; i++)
    {
      if (!Map[now].count(c[i]))
      {
        Map[now][c[i]] = ++to;
        Map[to].clear();
      }
      now = Map[now][c[i]];
    }
    cnt[now]++;
  }
  void getfail()
  {
    queue<int> p;
    fail[root] = root;
    for (it = Map[root].begin(); it != Map[root].end(); ++it)
    {
      fail[it->second] = root;
      p.push(it->second);
    }
    int now;
    while (!p.empty())
    {
      now = p.front();  p.pop();
      cnt[now] += cnt[fail[now]];
      for (it = Map[now].begin(); it != Map[now].end(); ++it)
      {
        int x = fail[now], flag = 0;
        while (x != root){
          if (Map[x].count(it->first)){
            fail[it->second] = Map[x][it->first];
            flag = 1;
            break;
          }
          x = fail[x];
        }
        if (x == root && Map[x].count(it->first)){
          fail[it->second] = Map[x][it->first];
          flag = 1;
        }
        if (!flag) fail[it->second] = root;
        p.push(it->second);
      }
    }
  }
  long long work()
  {
    getfail();
    long long ans = 0;
    int now = root;
    for (int i = 1; i < n; i++)
    {
      int x = now, flag = 0;
      while (x != root){
        if (Map[x].count(a[i])){
          now = Map[x][a[i]];
          flag = 1;
          break;
        } 
        x = fail[x];
      }
      if (x == root && Map[x].count(a[i])){
        now = Map[x][a[i]];
        flag = 1;
      }
      if (!flag) now = root;
      ans += cnt[now];
    }
    return ans;
  }
}ac;

int main()
{
  while (scanf("%d%d", &n, &m) != EOF)
  {
    tot = 0;  ac.clear();
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = n - 1; i; i--) a[i] = a[i] - a[i - 1];
    for (int i = 0; i < m; i++)
    {
      scanf("%d", &x);  
      for (int j = 0; j < x; j++) scanf("%d", &c[j]);
      for (int j = x - 1; j; j--) c[j] = c[j] - c[j - 1];
      if (x == 1) tot += n; else ac.insert(x);
    }
    printf("%lld\n", tot + ac.work());
  }
  return 0;
}