Assignment Task 1

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 20 15:56:04 2023

@author: ahsan
"""

def getZarr(string, z):
    n = len(string)

    # [L,R] make a window which matches
    # with prefix of s
    l, r, k = 0, 0, 0
    for i in range(1, n):

        # if i>R nothing matches so we will calculate.
        # Z[i] using naive way.
        if i > r:
            l, r = i, i

            # R-L = 0 in starting, so it will start
            # checking from 0'th index. For example,
            # for "ababab" and i = 1, the value of R
            # remains 0 and Z[i] becomes 0. For string
            # "aaaaaa" and i = 1, Z[i] and R become 5
            while r < n and string[r - l] == string[r]:
                r += 1
            z[i] = r - l
            r -= 1
        else:

            # k = i-L so k corresponds to number which
            # matches in [L,R] interval.
            k = i - l

            # if Z[k] is less than remaining interval
            # then Z[i] will be equal to Z[k].
            # For example, str = "ababab", i = 3, R = 5
            # and L = 2
            if z[k] < r - i + 1:
                z[i] = z[k]

            # For example str = "aaaaaa" and i = 2,
            # R is 5, L is 0
            else:

                # else start from R and check manually
                l = i
                while r < n and string[r - l] == string[r]:
                    r += 1
                z[i] = r - l
                r -= 1

def checkTransposition(text, pattern, zvalues, i):
    ### easier than expected
    size = len(pattern)
    currentIndex = i
    now = 0
    count = 0;
    first, second = -1, -1
    print(text[i:])
    print(zvalues[i:])

    while now < size and currentIndex < len(text):
        mn = min(zvalues[currentIndex], zvalues[now])

        now += mn
        currentIndex += mn

        if now >= size:
            break

        if currentIndex >= len(text):
            break

        if (text[currentIndex] == pattern[now]  and mn == 0):
            count+=0
        else:
            count+=1
            if count > 2:
                break
            if count == 1:
                first = currentIndex
            if count == 2:
                second = currentIndex


        print(now, currentIndex, mn, count)


        now += 1
        currentIndex += 1



        #print("second", now, currentIndex, mn, count)

        # if  zvalues[now] > zvalues[currentIndex]:
        #     continue



        # while now < size and currentIndex < len(text) and zvalues[now] == 0 and text[currentIndex] == pattern[now]:
        #     now += 1
        #     currentIndex += 1

        #print("second", now, currentIndex, mn, count)
        # if startIndex < len(text) and  zvalues[now] <= zvalues[currentIndex] and now + zvalues[now] == size-1:
        #     break



    #print(i, count, first, second)
    if count == 2:
        if text[first] == text[second-i] and text[second] == text[first-i]:
            print("answer", i, i-size, first-size, second-size)
        else:
            print("false", i, i-size, first-size, second-size)
    else:
        print(i, i-size,"false")

    print("=============")
    return False


def checkTranspositionNew(text, pattern, zvalues, i):
    ### easier than expected
    size = len(pattern)
    currentIndex = i
    now = 0
    count = 0;
    first, second = -1, -1
    #print(text[i:])
    #print(zvalues[i:])

    currentIndex +=  zvalues[currentIndex]
    now += zvalues[currentIndex]
    first = currentIndex
    second = currentIndex + 1

    if currentIndex == i + size - 1:
        return False




    if currentIndex < len(text) and now < size  and text[currentIndex] == pattern[now + 1] and text[currentIndex+1] == pattern[now]:
        #slide
        now += 2
        currentIndex += 2
        while now < size and currentIndex < len(text):
            if text[currentIndex] != pattern[now]:
                return False

            mn = min(zvalues[now], zvalues[currentIndex])
            if mn == 0:
                now += 1
                currentIndex += 1
            else:
                now += mn
                currentIndex += mn

        print(i-size, first-size)
        return True

    else:
        return False

    # while now < size and currentIndex < len(text):





    return False



# prints all occurrences of pattern
# in text using Z algo
def search(text, pattern):

    # Create concatenated string "P$T"
    concat = pattern + "$" + text
    l = len(concat)

    # Construct Z array
    z = [0] * l
    getZarr(concat, z)
    print(z)
    # now looping through Z array for matching condition
    for i in range(l):

        # if Z[i] (matched region) is equal to pattern
        # length we got the pattern
        if z[i] == len(pattern):
            print("Pattern found at index",
                      i - len(pattern))
            print("=============")
        elif i < l - len(pattern) + 1:
            checkTranspositionNew(concat, pattern, z, i)




search('babbababaabbaba','abba')