Problem:


Substring

長さnの文字列s=s1,s2,…,snおよびm個のクエリが与えられる。
各クエリqk (1 ≤ k ≤ m)は、"L++", "L--", "R++", "R--"の4種類のいずれかであり、
k番目のクエリqkに対してl[k]とr[k]を以下で定義する。

 L++：l[k]=l[k-1]+1,r[k]=r[k-1]

 L--：l[k]=l[k-1]-1,r[k]=r[k-1]

 R++：l[k]=l[k-1],r[k]=r[k-1]+1

 R--：l[k]=l[k-1],r[k]=r[k-1]-1

但し、l[0]=r[0]=1である。

この時、m個の部分文字列
sl[k], sl[k]+1, …, sr[k]-1, sr[k] (1 ≤ k ≤ m)
について、何種類の文字列が作られるかを答えよ。

Input

入力は以下の形式で与えられる

n m
s
q1
q2
…
qm

Constraints

 文字列sは小文字アルファベットからなる

 1 ≤ n ≤ 3×105

 1 ≤ m ≤ 3×105

 qk(1 ≤ k ≤ m)は、"L++"、"L--"、"R++"、"R--"のいずれか

 1 ≤ l[k] ≤ r[k] ≤ n (1 ≤ k ≤ m)

Output

問題の解を1行に出力せよ

Sample Input 1

5 4
abcde
R++
R++
L++
L--

Output for the Sample Input 1

3

l[1]=1, r[1]=2であり、部分文字列は"ab"である

l[2]=1, r[2]=3であり、部分文字列は"abc"である

l[3]=2, r[3]=3であり、部分文字列は"bc"である

l[4]=1, r[4]=3であり、部分文字列は"abc"である

よって、生成される文字列は{"ab","abc","bc"}の3種類である。

Sample Input 2

4 6
abab
R++
L++
R++
L++
R++
L++

Output for the Sample Input 2

4

l[1]=1, r[1]=2であり、部分文字列は"ab"である

l[2]=2, r[2]=2であり、部分文字列は"b"である

l[3]=2, r[3]=3であり、部分文字列は"ba"である

l[4]=3, r[4]=3であり、部分文字列は"a"である

l[5]=3, r[5]=4であり、部分文字列は"ab"である

l[6]=4, r[6]=4であり、部分文字列は"b"である

よって、生成される文字列は{"a","ab","b","ba"}の4種類である。

Sample Input 3

10 13
aacacbabac
R++
R++
L++
R++
R++
L++
L++
R++
R++
L--
L--
R--
R--

Output for the Sample Input 3

11



Sample input:
5 4
abcde
R++
R++
L++
L--


Sample output:
3

Submission status: Wrong Answer

Solution code:
def main():
  n, m = map(int, input().split())
  s = input()
  mem = set()
  base = ord("a") - 1
  mod1 = 1000000007
  mod2 = 2147483647
  left = right = 0
  score1 = score2 = ord(s[0]) - base
  pow_mem1 = {0:1}
  pow_mem2 = {0:1}
  def my_pow1(x):
    if x in pow_mem1:return pow_mem1[x]
    pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
    return pow_mem1[x]

  def my_pow2(x):
    if x in pow_mem2:return pow_mem2[x]
    pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
    return pow_mem2[x]

  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
      score1 = score1 // 27
      score2 = score2 // 27
    if com == "L--":
      left -= 1
      score1 = score1 * 27 + ord(s[left]) - base
      score2 = score2 * 27 + ord(s[left]) - base
    if com == "R++":
      right += 1
      score1 += my_pow1(right - left) * (ord(s[right]) - base)
      score2 += my_pow2(right - left) * (ord(s[right]) - base)
    if com == "R--":
      score1 -= my_pow1(right - left) * (ord(s[right]) - base)
      score2 -= my_pow2(right - left) * (ord(s[right]) - base)
      right -= 1
    score1 %= mod1
    score2 %= mod2
    if (score1, score2) not in mem:mem.add((score1, score2))
  print(len(mem))

main()

Submission status: Wrong Answer

Solution code:
class RollingHash:
    def __init__(self, s, base, MOD):
        self.s = s
        self.l = l = len(s)
        self.base = base
        self.MOD = MOD
        self.h = h = [0]*(l + 1)
        for i in xrange(l):
            h[i+1] = (h[i] * base + ord(s[i])) % MOD
    def get(self, l, r):
        MOD = self.MOD
        return ((self.h[r] - self.h[l]*pow(self.base, r-l, MOD) + MOD)) % MOD
n, m = map(int, raw_input().split())
s = raw_input()
h = RollingHash(s, 17, 10**9+7)
l = 0; r = 1
vs = set()
ans = 0
for i in xrange(m):
    q = raw_input()
    if q == "R++":
        r += 1
    elif q == "R--":
        r -= 1
    elif q == "L++":
        l += 1
    else:
        l -= 1
    v = h.get(l, r)
    if v not in vs:
        ans += 1
        vs.add(v)
print ans

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
left = right = 0
base = ord("a") - 1
score = ord(s[0]) - base
mem = set()
for _ in range(m):
  com = input()
  if com == "L++":
    score //= 27
    left += 1
  elif com == "L--":
    left -= 1
    score = score * 27 + ord(s[left]) - base
  elif com == "R++":
    right += 1
    score += 27 ** (right - left) * (ord(s[right]) - base)
  elif com == "R--":
    score -= 27 ** (right - left) * (ord(s[right]) - base)
    right -= 1
  if score not in mem:mem.add(score)
print(len(mem))

Submission status: Accepted

Solution code:
def main():
  n, m = map(int, input().split())
  s = input()
  mem = set()
  base = ord("a") - 1
  mod1 = 1000000007
  mod2 = 2147483647
  h1 = [0]
  h2 = [0]
  for c in s:
    h1.append((h1[-1] * 27 + ord(c) - base) % mod1)
    h2.append((h2[-1] * 27 + ord(c) - base) % mod2)
  pow_mem1 = {0:1}
  pow_mem2 = {0:1}
  def my_pow1(x):
    if x in pow_mem1:return pow_mem1[x]
    pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
    return pow_mem1[x]

  def my_pow2(x):
    if x in pow_mem2:return pow_mem2[x]
    pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
    return pow_mem2[x]
  
  left = right = 1
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    if com == "L--":
      left -= 1
    if com == "R++":
      right += 1
    if com == "R--":
      right -= 1
    x = (h1[right] - h1[left - 1] * my_pow1(right - left + 1)) % mod1
    y = (h2[right] - h2[left - 1] * my_pow2(right - left + 1)) % mod2
    mem.add((x, y))

  print(len(mem))

main()

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self, s, base, MOD):
        self.s = s
        self.l = l = len(s)
        self.base = base
        self.MOD = MOD
        self.h = h = [0]*(l + 1)
        for i in xrange(l):
            h[i+1] = (h[i] * base + ord(s[i])) % MOD
    def get(self, l, r):
        MOD = self.MOD
        return ((self.h[r] - self.h[l]*pow(self.base, r-l, MOD) + MOD)) % MOD
n, m = map(int, raw_input().split())
s = raw_input()
h1 = RollingHash(s, 13, 10**9+7)
h2 = RollingHash(s, 17, 10**9+7)
l = 0; r = 1
vs = set()
ans = 0
for i in xrange(m):
    q = raw_input()
    if q == "R++":
        r += 1
    elif q == "R--":
        r -= 1
    elif q == "L++":
        l += 1
    else:
        l -= 1
    v = (h1.get(l, r), h2.get(l, r))
    if v not in vs:
        ans += 1
        vs.add(v)
print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
base = long(1e9+7)
mod  = long(2**64-1)

# a x + b y = gcd(a, b)
def extgcd(a, b, x, y):
    g, x, y = a, 1, 0
    if b != 0:
        g, y, x = extgcd(b, a % b, y, x)
        y -= int(a / b) * x
    return [g, x, y];


def invMod(a, m=mod):
    g, x, y = 1, 1, 0
    g, x, y = extgcd(a, m, x, y)
    if g == 1:
        return (x + mod) % mod
    else:
        return 0 #unsolvable

if __name__ == '__main__':
    n, m = map(long, raw_input().split(' '))
    s = raw_input()
    r, l = 1, 0
    vb = [1]
    for i in xrange(n):
        vb.append(long(vb[i]*base)%mod)
        
    inv = invMod(base)
    val = long(ord(s[0]))
    bucket = set()
    for i in xrange(m):
        ss = raw_input()
        if ss == "R++":
            val = (val*base + ord(s[r]))%mod
            r+=1
        elif ss == "R--":
            val = (val + mod - ord(s[r - 1]))%mod
            val = val*inv%mod
            r-=1
        elif ss == "L++":
            val = (val + mod - ord(s[l])*vb[r - l - 1]%mod)%mod
            l+=1
        else:
            val = (val + ord(s[l - 1])*vb[r - l])%mod
            l-=1
        
        bucket.add(val);
        #print ss, s[l:r], val, len(bucket)
    print len(bucket)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)
MOD = 10 ** 30 + 7

N, M = map(int, raw_input().split())
s = raw_input()

p27 = [1 for i in range(500000)]
for i in range(1, 500000):
    p27[i] = p27[i - 1] * 27
    p27[i] %= MOD

m = {}
P = (ord(s[0]) - ord('a') + 1)
l = 0
r = 0
for loop in range(M):
    S = raw_input()
    if S == 'L++':
        P -= (ord(s[l]) - ord('a') + 1) * p27[r - l]
        P %= MOD
        l += 1
    elif S == 'L--':
        l -= 1
        P += (ord(s[l]) - ord('a') + 1) * p27[r - l]
        P %= MOD
    elif S == 'R++':
        r += 1
        P *= 27
        P += (ord(s[r]) - ord('a') + 1)
        P %= MOD
    elif S == 'R--':
        P -= (ord(s[r]) - ord('a') + 1)
        P %= MOD
        for i in range(27):
            if (P + MOD * i) % 27 == 0:
                P = (P + MOD * i) / 27
                break
        r -= 1
    #print s[l:r + 1], P
    m[P] = 1
print len(m)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)
MOD = 10 ** 30 + 7

N, M = map(int, raw_input().split())
s = raw_input()

p27 = [1 for i in range(500000)]
for i in range(1, 500000):
    p27[i] = p27[i - 1] * 27
    p27[i] %= MOD

m = {}
P = (ord(s[0]) - ord('a') + 1)
l = 0
r = 0
for loop in range(M):
    S = raw_input()
    if S == 'L++':
        P -= (ord(s[l]) - ord('a') + 1) * p27[r - l]
        P %= MOD
        l += 1
    elif S == 'L--':
        l -= 1
        P += (ord(s[l]) - ord('a') + 1) * p27[r - l]
        P %= MOD
    elif S == 'R++':
        r += 1
        P *= 27
        P += (ord(s[r]) - ord('a') + 1)
        P %= MOD
    elif S == 'R--':
        P -= (ord(s[r]) - ord('a') + 1)
        P %= MOD
        for i in range(27):
            if (P + MOD * i) % 27 == 0:
                P = (P + MOD * i) / 27
                break
        r -= 1
    m[P] = 1
print len(m)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
MOD = 10 ** 30 + 7

N, M = map(int, raw_input().split())
s = raw_input()

p27 = [1 for i in range(500000)]
for i in range(1, 500000):
    p27[i] = p27[i - 1] * 27
    p27[i] %= MOD

m = {}
P = (ord(s[0]) - ord('a') + 1)
l = 0
r = 0
for loop in range(M):
    S = raw_input()
    if S == 'L++':
        P -= (ord(s[l]) - ord('a') + 1) * p27[r - l]
        P %= MOD
        l += 1
    elif S == 'L--':
        l -= 1
        P += (ord(s[l]) - ord('a') + 1) * p27[r - l]
        P %= MOD
    elif S == 'R++':
        r += 1
        P *= 27
        P += (ord(s[r]) - ord('a') + 1)
        P %= MOD
    elif S == 'R--':
        P -= (ord(s[r]) - ord('a') + 1)
        P %= MOD
        for i in range(27):
            if (P + MOD * i) % 27 == 0:
                P = (P + MOD * i) / 27
                break
        r -= 1
    m[P] = 1
print len(m)

Submission status: Accepted

Solution code:
import random
n,m = map(int,input().split())
s = input()

#s[i:j]のハッシュ値:(hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1,(hash2[j]-hash2[i]*power2[j-i]%mod2)%mod2
#長さnの文字列s
base1 = 1007
mod1 = 10**9+7

base2 = 2009
mod2 = 10**9+9

modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
modTank2 = [3000014753,3000014783,3000014833,3000014839,3000014891,3000015433]
mod2 = modTank2[random.randint(0,5)]


hash1 = [0]*(n+1)
power1 = [1]*(n+1)

hash2 = [0]*(n+1)
power2 = [1]*(n+1)


for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

    hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
    power2[i+1] = (power2[i]*base2)%mod2

res = 0

tank1 = set()
L = 0
R = 1
for _ in range(m):
    q = input()
    if q == 'L++':
        L += 1
    elif q == 'L--':
        L -= 1
    elif q == 'R++':
        R += 1
    else:
        R -= 1
    hashData1 = ((hash1[R]-hash1[L]*power1[R-L]%mod1)%mod1)*(10**10) + (hash2[R]-hash2[L]*power2[R-L]%mod2)%mod2

    if hashData1 in tank1:
        res += 1
    
    tank1.add(hashData1)
print(len(tank1))

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


class RollingHash:
    def __init__(self, s, base, mod):
        self.s = s
        self.length = length = len(s)
        self.base = base
        self.mod = mod
        self.h = h = [0] * (length + 1)
        for i in range(length):
            h[i + 1] = (h[i] * base + ord(s[i])) % mod
        self.p = p = [1] * (length + 1)
        for i in range(length):
            p[i + 1] = pow(base, i + 1, mod)

    def get(self, l, r):
        mod = self.mod
        # return (self.h[r] - self.h[l] * pow(self.base, r - l, mod) + mod) % mod
        return ((self.h[r] - self.h[l] * self.p[r - l]) + mod) % mod


def solve():
    N, M = inpl()
    S = input()
    h1 = RollingHash(S, 13, MOD)
    h2 = RollingHash(S, 17, MOD)
    left, right = 0, 1
    vs = set()
    ans = 0
    for i in range(M):
        q = input()
        if q == 'R++':
            right += 1
        elif q == 'R--':
            right -= 1
        elif q == 'L++':
            left += 1
        else:
            left -= 1

        v = (h1.get(left, right), h2.get(left, right))
        if v not in vs:
            ans += 1
            vs.add(v)

    return ans


print(solve())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def M(n): return ModInt(n)

class RollingHash():
    def __init__(self, s):
        self.N = n = len(s)
        a = [ord(c) for c in s]
        self.A1 = a1 = [M(a[0])]
        self.A2 = a2 = [M(a[0])]
        for c in a[1:]:
            a1.append(a1[-1] * 997 + c)
            a2.append(a2[-1] * 991 + c)

    def get(self, l, r):
        if l == 0:
            return (self.A1[r].n, self.A2[r].n)
        t1 = (self.A1[r] - self.A1[l-1] * pow(997, r-l+1, mod)).n
        t2 = (self.A2[r] - self.A2[l-1] * pow(991, r-l+1, mod)).n
        return (t1, t2)

def main():
    rr = []

    def f(n,m):
        rs = set()
        s = S()
        qa = [S() for _ in range(m)]
        l = 0
        r = 0
        rh = RollingHash(s)
        for q in qa:
            if q == 'L++':
                l += 1
            elif q == 'L--':
                l -= 1
            elif q == 'R++':
                r += 1
            else:
                r -= 1
            rs.add((l,r))

        rrs = set()
        for l, r in rs:
            rrs.add(rh.get(l,r))
        return len(rrs)

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        # print('rr', rr[-1])
        break

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
def main():
  n, m = map(int, input().split())
  s = input()
  left = right = 0
  mem = set()
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    elif com == "L--":
      left -= 1
    elif com == "R++":
      right += 1
    elif com == "R--":
      right -= 1
    mem.add(s[left:right + 1])
  print(len(mem))

main()