from docx import Document

document = Document()

from docx import Document

document = Document('myfile.docx')
document.save('new-file-name.docx')

document.add_heading('新建标题', level=1)

paragraph = document.add_paragraph('新建段落。')

paragraph = document.add_paragraph('这是一个样式为 ListBullet 的段落')
paragraph.style = 'List Bullet'

from docx.enum.text import WD_ALIGN_PARAGRAPH

# LEFT      =>  左对齐
# CENTER    =>  文字居中
# RIGHT     =>  右对齐
# JUSTIFY   =>  文本两端对齐

paragraph = document.add_paragraph("对其方式测试")
paragraph_format = paragraph.paragraph_format
paragraph_format.alignment = WD_ALIGN_PARAGRAPH.CENTER

from docx.shared import Inches

paragraph = document.add_paragraph("这是缩进")
paragraph.paragraph_format.left_indent = Inches(0.5)

paragraph.paragraph_format.first_line_indent = Inches(0.5)

from docx.enum.text import WD_LINE_SPACING

#SINGLE         =>  单倍行距（默认）
#ONE_POINT_FIVE =>  1.5倍行距
#DOUBLE2        =>  倍行距
#AT_LEAST       =>  最小值
#EXACTLY        =>  固定值
#MULTIPLE       =>  多倍行距

paragraph.line_spacing_rule = WD_LINE_SPACING.EXACTLY #固定值
paragraph.paragraph_format.line_spacing = Pt(18) # 固定值18磅
paragraph.line_spacing_rule = WD_LINE_SPACING.MULTIPLE #多倍行距
paragraph.paragraph_format.line_spacing = 1.75 # 1.75倍行间距

paragraph = document.add_paragraph()
paragraph.add_run('这是一个带有')
paragraph.add_run('粗体').bold = True
paragraph.add_run('和')
paragraph.add_run('斜体').italic = True
paragraph.add_run('的段落。')

def generate_doc(namelist):

    # 授权正文
    content = '兹委托  xxx （身份证件号：xxxxxxxxxxxxx）' \
           '到xx机关办理xx业务事项。委托人和代理人严格遵守有关xx法律法规。'



    # 以下为生成保密协议的代码，name_list中的每个人员都将生成对应一份保密协议文档
    for names in name_list:
        # 创建内存中的word文档对象
        file = docx.Document()
        file.styles['Normal'].font.name = u'宋体'
        file.styles['Normal']._element.rPr.rFonts.set(qn('w:eastAsia'), u'宋体')  # 可换成word里面任意字体



        # 写入若干段落
        p1 = file.add_paragraph()
        p1.paragraph_format.alignment = WD_ALIGN_PARAGRAPH.CENTER  # 段落文字居中设置
        run = p1.add_run("办理xx事项授权委托书")
        run.font.size = docx.shared.Pt(20)
        run.bold = True

        # 抬头
        head = file.add_paragraph()
        head.paragraph_format.alignment = WD_ALIGN_PARAGRAPH.LEFT
        run = head.add_run("\n\nxx市xx区xx局：\n")
        run.font.size = docx.shared.Pt(14)   # 四号字体
        run.bold = True

        # 个人信息
        p2 = file.add_paragraph()
        # p2.line_spacing_rule = WD_LINE_SPACING.ONE_POINT_FIVE
        p2.paragraph_format.line_spacing_rule = WD_LINE_SPACING.DOUBLE
        p2.paragraph_format.first_line_indent = Inches(0.5)
        p2.add_run('本人，').font.size = docx.shared.Pt(14)
        run = p2.add_run('%s' % names[0])
        run.font.size = docx.shared.Pt(14)

        p2.add_run('（身份证件号：').font.size = docx.shared.Pt(14)
        run = p2.add_run('%s）' % names[1])
        run.font.size = docx.shared.Pt(14)

        p2.add_run(content + '\n').font.size = docx.shared.Pt(14)

        p3 = file.add_paragraph()
        run = p3.add_run('委托人签名：                     代理人签名：\n')
        run.font.size = docx.shared.Pt(14)
        run.bold = True

        p5 = file.add_paragraph()
        p5.paragraph_format.alignment = WD_ALIGN_PARAGRAPH.RIGHT

        run = p5.add_run("2021 年 5 月")
        run.font.size = docx.shared.Pt(14)
        run.bold = True

        # 保存
        file.save("./result/办理xx事项授权委托书-%s.docx" % names[0])

def countPrimes(n):
    '''
    输出 <= n 的质数个数
    :param n: 整数
    :return: 质数个数
    '''
    if n < 2:
        return 0

    isPrime = [True] * (n + 1)
    isPrime[0] = isPrime[1] = False
    i = 2
    while i * i <= n:
        if isPrime[i]:
            for j in range(i*i, n+1, i):
                isPrime[j] = False
        i += 1

    cnt = 0
    for flag in isPrime:
        if flag:
            cnt += 1
    return cnt

class Solution:
    def countPrimes(self, n: int) -> int:
        '''
        返回小于 n 的质数个数
        :param n:
        :return:
        '''
        if n <= 2:
            return 0

        isPrime = [True] * (n)
        isPrime[0] = isPrime[1] = False
        i = 2
        while i * i < n:
            if isPrime[i]:
                for j in range(i*i, n, i):
                    isPrime[j] = False
            i += 1

        cnt = 0
        for flag in isPrime:
            if flag:
                cnt += 1
        return cnt

def myPow(x: float, n: int) -> float:
    res = 1.0
    base = x
    e = abs(n)
    while e:
        if e & 1 == 1:
            res *= base

        base *= base
        e >>= 1
    return res if n >= 0 else 1.0 / res

class Solution:
    def myPow(self, x: float, n: int) -> float:

        def quick_pow(x, n):
            base = x
            ans = 1

            while n:
                if n & 1:
                    ans *= base

                base *= base
                n >>= 1
            
            return ans
        return quick_pow(x, n) if n > 0 else 1/quick_pow(x, abs(n))

def addStrings(self, num1: str, num2: str) -> str:
    '''
    大数加法
    '''
    res = ""
    i, j, carry = len(num1) - 1, len(num2) - 1, 0
    while i >= 0 or j >= 0:
        # 高位补零
        n1 = int(num1[i]) if i >= 0 else 0
        n2 = int(num2[j]) if j >= 0 else 0
        tmp = n1 + n2 + carry
        carry = tmp // 10
        res = str(tmp % 10) + res
        i, j = i - 1, j - 1
    return "1" + res if carry else res

def multiply(num1, num2):
    product = [0] * (len(num1) + len(num2))  # placeholder for multiplication ndigit by mdigit result in n+m digits
    position = len(product) - 1  # position within the placeholder

    for n1 in num1[::-1]:
        tempPos = position
        for n2 in num2[::-1]:
            product[tempPos] += int(n1) * int(n2)  # ading the results of single multiplication
            product[tempPos - 1] += product[tempPos] // 10  # bring out carry number to the left array
            product[tempPos] %= 10  # remove the carry out from the current array
            tempPos -= 1  # first shifting the multplication to the end of the first integer
        position -= 1  # then once first integer is exhausted shifting the second integer and starting

    # once the second integer is exhausted we want to make sure we are not zero padding
    pointer = 0  # pointer moves through the digit array and locate where the zero padding finishes
    while pointer < len(product) - 1 and product[
        pointer] == 0:  # if we have zero before the numbers shift the pointer to the right
        pointer += 1

    return ''.join(map(str, product[pointer:]))  # only report the digits to the right side of the pointer

def gcd(a, b):
    '''
    这里不用判断a, b的相对大小,如果 a < b, 在递归调用 gcd(b, a%b)时
    自动调换了顺序。
    '''
    if b == 0:
        return a
    return gcd(b, a % b)

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def gcd(a, b):
            if b == 0:
                return a
            return gcd(b, a % b)

        res = []
        for i in range(2, n+1):
            for j in range(1, i):
                if gcd(j, i) == 1:
                    res.append(str(j) + '/' + str(i))
        return res

def lcm(a, b):
    return a * b // gcd(a, b)

# 当分支逻辑不能排除右边界，选左中位数，如果选右中位数则会出现死循环
def binary_search1(left, right):
    while left < right:
        mid = (left + right) >> 1
        if check(mid):
            left = mid + 1
        else:
            right = mid
    # 退出循环的时候， 视情况，是否需要单独判断left是否满足条件
    return left

def binary_search2(left, right):
    while left < right:
        # 选择右中位数
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                right = mid - 1
            else:
                left = mid
    # 退出循环的时候， 视情况，是否需要单独判断left是否满足条件
    return left

parent = list(range(N))

def find(x):
    if x != parent[x]:
        # 路径完全压缩
        parent[x] = find(parent[x])
        
    return parent[x]

def union(x, y):
    root1 = find(x)
    root2 = find(y)
    parent[root2] = root1

class DSU:
    def __init__(self, N):
        self.parent = list(range(N+1))
        self.edges = 0

    def find(self, x):
        if x != self.parent[x]:
            # 路径完全压缩
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    def union(self, x, y):
        root1 = self.find(x)
        root2 = self.find(y)
        
        self.parent[root2] = root1
        self.edges += 1

def kruskal():
    '''
    适用于求稀疏图
    :return: 最小生成树的边和
    '''
    cost = 0
    for u, v, w in sorted(edges, key=lambda x: x[2]):
        pu, pv = find(u), find(v)
        if pu == pv:
            continue
        # 等同于union
        parent[pu] = pv
        cost += w
    return cost

n = 4
edges = [[0, 1, 1], [0, 3, 3], [0, 2, 6], [2, 3, 2], [1, 2, 4]]

parent = list(range(n))

def find(x):
    if x != parent[x]:
        # 路径完全压缩
        parent[x] = find(parent[x])

    return parent[x]


def union(x, y):
    root1 = find(x)
    root2 = find(y)
    parent[root2] = root1


def kruskal():
    '''
    适用于求稀疏图
    :return: 最小生成树的边和
    '''
    cost = 0
    for u, v, w in sorted(edges, key=lambda x: x[2]):
        pu, pv = find(u), find(v)
        if pu == pv:
            continue
        # 等同于union
        parent[pu] = pv
        cost += w
    return cost

def prime():
    '''
    适用于稠密图，堆优化版本
    :return: cost
    '''
    q = []
    cost = 0
    seen = set()
    # push a dummy node, (cost, node)
    heappush(q, (0, 0))

    for _ in range(n):
        w, u = heappop(q)
        if u in seen:
            continue
        cost += w
        seen.add(u)
        for v, w in graph[u]:
            if v in seen:
                continue
            heappush(q, (w, v))
    return cost

from collections import defaultdict
from heapq import *

n = 4 # 顶点数
edges = [[0, 1, 1], [0, 3, 3], [0, 2, 6], [2, 3, 2], [1, 2, 4]]

graph = defaultdict(list)
for e in edges:
    graph[e[0]].append((e[1], e[2]))
    graph[e[1]].append((e[0], e[2]))

def prime():
    '''
    适用于稠密图，堆优化版本
    :return: cost
    '''
    q = []
    cost = 0
    seen = set()
    # push a dummy node, (cost, node)
    heappush(q, (0, 0))

    for _ in range(n):
        w, u = heappop(q)
        if u in seen:
            continue
        cost += w
        seen.add(u)
        for v, w in graph[u]:
            if v in seen:
                continue
            heappush(q, (w, v))
    return cost

print(prime())
# 6

def dijkstra(graph, source, N):
    '''
    单源最短路径算法
    :param graph: 邻接矩阵，或者用字典实现
    :param source: 起始点
    :param N: 节点个数
    :return:
    '''
    # 如果是node 是 1-indexed
    dist = [float('inf')] * (N + 1)
    prev = [-1] * (N + 1)

    dist[source] = dist[0] = 0

    hq = [(0, source)]
    while hq:
        d, u = heapq.heappop(hq)
        for v in graph[u]:
            alt = dist[u] + graph[u][v]
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heapq.heappush(hq, (alt, v))
    return dist, prev

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        # construct graph
        graph = collections.defaultdict(dict)
        for u, v, time in times:
            graph[u][v] = time


        def dijkstra(graph, source, N):
            '''
            单源最短路径算法
            :param graph: 邻接矩阵，或者用字典实现
            :param source: 起始点
            :return:
            '''
            dist = [float('inf')] * (N + 1)
            prev = [-1] * (N + 1)

            # 如果是node 是 1-indexed
            dist[source] = dist[0] = 0
            
            hq = [(0, source)]
            while hq:
                d, u = heapq.heappop(hq)
                for v in graph[u]:
                    alt = dist[u] + graph[u][v]
                    if alt < dist[v]:
                        dist[v] = alt
                        prev[v] = u
                        heapq.heappush(hq, (alt, v))
            return dist, prev
        
        dist, _ = dijkstra(graph, K, N)
        # print(dist)
        ans = max(dist)
        return ans if ans != float('inf') else -1

# Python3 program for Bellman-Ford's single source
# shortest path algorithm.

# Class to represent a graph
class Graph:

    def __init__(self, vertices):
        self.V = vertices  # No. of vertices
        self.graph = []


    # function to add an edge to graph
    def addEdge(self, u, v, w):
        self.graph.append([u, v, w])


    # utility function used to print the solution
    def printArr(self, dist):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print("{0}\t\t{1}".format(i, dist[i]))

    # The main function that finds shortest distances from src to
    # all other vertices using Bellman-Ford algorithm. The function
    # also detects negative weight cycle
    def BellmanFord(self, src):

        # Step 1: Initialize distances from src to all other vertices
        # as INFINITE
        dist = [float("Inf")] * self.V
        dist[src] = 0

        # Step 2: Relax all edges |V| - 1 times. A simple shortest
        # path from src to any other vertex can have at-most |V| - 1
        # edges
        for _ in range(self.V - 1):
            # Update dist value and parent index of the adjacent vertices of
            # the picked vertex. Consider only those vertices which are still in
            # queue
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        # Step 3: check for negative-weight cycles. The above step
        # guarantees shortest distances if graph doesn't contain
        # negative weight cycle. If we get a shorter path, then there
        # is a cycle.

        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        # print all distance
        self.printArr(dist)


g = Graph(5)
g.addEdge(0, 1, -1)
g.addEdge(0, 2, 4)
g.addEdge(1, 2, 3)
g.addEdge(1, 3, 2)
g.addEdge(1, 4, 2)
g.addEdge(3, 2, 5)
g.addEdge(3, 1, 1)
g.addEdge(4, 3, -3)

# Print the solution
g.BellmanFord(0)

# Initially, Contributed by Neelam Yadav
# Later On, Edited by Himanshu Garg

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dist = [float("inf") for _ in range(N)]
        dist[K-1] = 0
        for _ in range(N-1):
            for u, v, w in times:
                if dist[u-1] + w < dist[v-1]:
                    dist[v-1] = dist[u-1] + w
        return max(dist) if max(dist) < float("inf") else -1

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dist = [float("inf") for _ in range(N)]
        K -= 1
        dist[K] = 0
        weight = collections.defaultdict(dict)
        for u, v, w in times:
            weight[u-1][v-1] = w
        
        queue = collections.deque([K])
        while queue:
            u = queue.popleft()
            for v in weight[u]:
                if dist[u] + weight[u][v] < dist[v]:
                    dist[v] = dist[u] + weight[u][v]
                    queue.append(v)
        return max(dist) if max(dist) < float("inf") else -1

def floyd_warshall(graph, N):
    '''
    :param graph: 邻接矩阵
    :param N: 节点数
    :return: 修改过的邻接矩阵
    '''
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        # construct graph
        dist = [[float("inf") for _ in range(N)] for _ in range(N)]
        for u, v, w in times:
            dist[u - 1][v - 1] = w
        for i in range(N):
            dist[i][i] = 0

        def floyd_warshall(graph, N):
            '''
            :param graph: 邻接矩阵 
            :param N: 节点数
            :return: 修改过的邻接矩阵
            '''
            for k in range(N):
                for i in range(N):
                    for j in range(N):
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        floyd_warshall(dist, N)
        return max(dist[K - 1]) if max(dist[K - 1]) < float("inf") else -1

import collections


def isBipartite(graph):
    n = len(graph)
    UNCOLORED, RED, GREEN = 0, 1, 2
    color = [UNCOLORED] * n

    # graph 不一定是连通图
    for i in range(n):
        if color[i] == UNCOLORED:
            q = collections.deque([i])
            color[i] = RED
            while q:
                node = q.popleft()
                cNei = (GREEN if color[node] == RED else RED)
                for neighbor in graph[node]:
                    if color[neighbor] == UNCOLORED:
                        q.append(neighbor)
                        color[neighbor] = cNei
                    elif color[neighbor] != cNei:
                        return False, None

    return True, color

graph = [[1,3], [0,2], [1,3], [0,2]]
print(isBipartite(graph))
'''
(True, [1, 2, 1, 2])
'''

class DFS_hungary():
    # https://www.icode9.com/content-1-615590.html
    # 参数初始化
    def __init__(self, set_A, set_B, edge, cx, cy, visited):
        self.set_A, self.set_B = set_A, set_B  # 顶点集合
        self.edge = edge  # 顶点是否连边
        self.cx, self.cy = cx, cy  # 顶点是否匹配
        self.visited = visited  # 顶点是否被访问
        self.M = []  # 匹配
        self.res = 0  # 匹配数

    # 遍历顶点A集合，得到最大匹配
    def max_match(self):
        for i in self.set_A:
            if self.cx[i] == -1:  # 未匹配
                for key in self.set_B:  # 将visited置0表示未访问过
                    self.visited[key] = 0
                self.res += self.path(i)
                print('i', i, 'M',self.M)


    # 增广路置换获得更大的匹配
    def path(self, u):
        for v in self.set_B:
            if self.edge[u][v] and (not self.visited[v]):  # 如果可连且未被访问过
                self.visited[v] = 1 # 访问该顶点
                if self.cy[v] == -1:  # 如果未匹配， 则建立匹配
                    self.cx[u], self.cy[v] = v, u
                    self.M.append((u, v))
                    return 1
                else:
                    self.M.remove((self.cy[v], v))  # 如果匹配则删除之前的匹配
                    if self.path(self.cy[v]):  # 递归调用
                        self.cx[u], self.cy[v] = v, u
                        self.M.append((u, v))
                        return 1
            print('v', v, 'M', self.M)
        return 0


if __name__ == '__main__':
    set_A, set_B = ['A', 'B', 'C', 'D'], ['E', 'F', 'G', 'H']
    edge = {'A': {'E': 1, 'F': 0, 'G': 1, 'H': 0}, 'B': {'E': 0, 'F': 1, 'G': 0, 'H': 1},
            'C': {'E': 1, 'F': 0, 'G': 0, 'H': 1}, 'D': {'E': 0, 'F': 0, 'G': 1, 'H': 0}}  # 1表示可以匹配，0表示不能匹配
    cx, cy = {'A': -1, 'B': -1, 'C': -1, 'D': -1}, {'E': -1, 'F': -1, 'G': -1, 'H': -1}
    visited = {'E': 0, 'F': 0, 'G': 0, 'H': 0}
    dh = DFS_hungary(set_A, set_B, edge, cx, cy, visited)
    dh.max_match()
    print('res', dh.res)
    print('cx', cx)
    print('cy', cy)
    print('visited', visited)

# 结果显示：
# i A M [('A', 'E')]  # 对于E点，可与A点连接，第一次匹配，直接在max_match打印，存在增广路：CEAG
# v E M [('A', 'E')]  # 对于E点，不能和B点连接，在path中打印
# i B M [('A', 'E'), ('B', 'F')]  # 对于F点，可与B点连接，直接在max_match打印，匹配数增加，存在增广路：CEAG
# v E M [('B', 'F')]  # 对于E点，可以与C连接，但已经与A点连接，从M中移除AE，在path中打印，进入递归内部
# v F M [('B', 'F')]
# i C M [('B', 'F'), ('A', 'G'), ('C', 'E')]  # 对于G点，可与A点连接，直接在max_match打印，匹配数增加，存在增广路：DGAECH
# v E M [('B', 'F'), ('A', 'G'), ('C', 'E')]  # 对于E点，不能与D点连接，在path中打印
# v F M [('B', 'F'), ('A', 'G'), ('C', 'E')]  # 对于F点，不能与D点连接，在path中打印
# v E M [('B', 'F')]  # 对于G点，可以与D连接，但已经与A点连接，从M中移除AG，在path中打印，进入递归内部，继续移除CE
# v F M [('B', 'F')]
# v G M [('B', 'F')]
# i D M [('B', 'F'), ('C', 'H'), ('A', 'E'), ('D', 'G')] # 无增广路
# res 4
# cx {'A': 'E', 'B': 'F', 'C': 'H', 'D': 'G'}
# cy {'E': 'A', 'F': 'B', 'G': 'D', 'H': 'C'}
# visited {'E': 1, 'F': 0, 'G': 1, 'H': 1}

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        s = sum(nums)

        if s % 2:
            return False

        capacity = s // 2
        dp = [False] * (capacity + 1)
        dp[0] = True

        for i in range(1, n+1):
            for j in range(capacity, nums[i-1]-1, -1):
                dp[j] = dp[j] or dp[j - nums[i-1]]
    
        return dp[capacity]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                dp[j] = min(dp[j], 1 + dp[j - coins[i]])
        return dp[amount] if dp[amount] != float('inf') else -1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)

        dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[-1][-1]

# Python program for KMP Algorithm
def KMPSearch(pat, txt):
    M = len(pat)
    N = len(txt)

    if M == 0:
        return 0

    # create lps[] that will hold the longest prefix suffix
    # values for pattern
    lps = [0] * M
    j = 0  # index for pat[]

    # Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps)

    i = 0  # index for txt[]
    while i < N:
        if pat[j] == txt[i]:
            i += 1
            j += 1

        if j == M:
            # print("Found pattern at index " + str(i-j))
            return i - j
            j = lps[j - 1]

        # mismatch after j matches
        elif i < N and pat[j] != txt[i]:
            # Do not match lps[0..lps[j-1]] characters,
            # they will match anyway
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

def computeLPSArray(pat, M, lps):
    len = 0  # length of the previous longest prefix suffix

    lps[0]  # lps[0] is always 0
    i = 1

    # the loop calculates lps[i] for i = 1 to M-1
    while i < M:
        if pat[i] == pat[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            # This is tricky. Consider the example.
            # AAACAAAA and i = 7. The idea is similar
            # to search step.
            if len != 0:
                len = lps[len - 1]

                # Also, note that we do not increment i here
            else:
                lps[i] = 0
                i += 1


txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
print(KMPSearch(pat, txt))

# This code is contributed by Bhavya Jain

class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for letter in word:
            current = current.children[letter]
        current.is_word = True

    def search(self, word):
        current = self.root
        for letter in word:
            current = current.children.get(letter)
            if current is None:
                return False
        return current.is_word

    def startsWith(self, prefix):
        current = self.root
        for letter in prefix:
            current = current.children.get(letter)
            if current is None:
                return False
        return True

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


class NumArray:
    def __init__(self, nums: List[int]):
        # helper function to create a segment tree
        def create_tree(left, right, nums):
            if left > right:
                return None

            if left == right:
                node = Node(left, right)
                node.total = nums[left]
                return node

            mid = (left + right) // 2

            node = Node(left, right)

            node.left = create_tree(left, mid, nums)
            node.right = create_tree(mid + 1, right, nums)

            node.total = node.left.total + node.right.total

            return node

        self.root = create_tree(0, len(nums) - 1, nums)

    def update(self, i: int, val: int) -> None:

        def update_tree(root, i, val):

            if root.start == root.end and root.start == i:
                root.total = val
                return

            mid = (root.start + root.end) // 2

            if i <= mid:
                update_tree(root.left, i, val)

            else:
                update_tree(root.right, i, val)

            root.total = root.left.total + root.right.total

        update_tree(self.root, i, val)

    def sumRange(self, i: int, j: int) -> int:

        def get_sum(root, i, j):

            if root.start == i and root.end == j:
                return root.total

            mid = (root.start + root.end) // 2

            # in left tree
            if j <= mid:
                return get_sum(root.left, i, j)
            elif mid < i:
                return get_sum(root.right, i, j)
            else:
                l_s = get_sum(root.left, i, mid)
                r_s = get_sum(root.right, mid + 1, j)
                return l_s + r_s

        return get_sum(self.root, i, j)

class FenwickTree:
    def __init__(self, n):
        self.sums_ = [0] * (n + 1)
    
    def update(self, i, delta):
        while i < len(self.sums_):
            self.sums_[i] += delta
            i += self.lowbit(i)
    
    def query(self, i):
        sum_ = 0
        while i > 0:
            sum_ += self.sums_[i]
            i -= self.lowbit(i)
        return sum_
    
    def lowbit(self, x):
        return x & (-x)