Similar Strings

Problem Statement :

Jimmy loves playing with strings. He thinks string  A is similar to string B if the following conditions are satisfied:

Both strings have the same length (i.e.,  and ).
For each valid pair of indices, , in the strings,  and  or  and .
For example, string  and  are similar as for ,  and  and for all other  pairs  as well as .

He has a string, , of size  and gives you  queries to answer where each query is in the form of a pair of integers . For each substring , find the number of substrings  where substring  is similar to substring  and print this number on a new line.

Note: Substring  is the contiguous sequence of characters from index  to index . For example, if  abcdefgh, then  cdef.

Input Format

The first line contains two space-separated integers describing the respective values of  and .
The second line contains string .
Each line  of the  subsequent lines contains two space-separated integers describing the respective values of  and  for query .


Output Format

For each query, print the number of similar substrings on a new line.

Solution :

                            Solution in C :

In   C++  :








/*
*/

//#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 150031;

int n, tests;
string st;
int used[N];
int mapp[N];
vector<int> v;
int whr[N];

int pw[N];

int S[200000][15];

int maps1[200], maps2[200];

vector<int> entries[100];
int maps[4][100];

int FE[N][15];

void run_mapper(int a,int b)
{
vector<pair<int, int> > O;

for (int i = 0; i < 10; i++)
{
int whr = FE[a][i];
O.push_back(make_pair(whr, i));
}
sort(O.begin(), O.end());
for (int i = 0; i < O.size(); i++)
{
maps[b][O[i].second] = i;
}
}

int get_hash(int a, int span, int tp)
{
int res = 0;
for (int i = 0; i < 10; i++)
{
int here = S[a+span][i] - S[a][i];
here *= (maps[tp][i]+1);
here *= pw[N - a - 1];
res += here;
}
return res;
}

int lcp(int a, int b)
{
run_mapper(a, 1);
run_mapper(b, 2);
/*for (int i = 0; i < 10; i++)
{
cout << maps[1][i] << " ";
}
cout << endl;
for (int i = 0; i < 10; i++)
{
cout << maps[2][i] << " ";
}
cout << endl;
*/
int l, r;
l = 0;
r = st.size() - max(a, b);
while (l < r)
{
int mid = l + r + 1;
mid /= 2;
long long H1 = get_hash(a, mid,1);
long long H2 = get_hash(b, mid,2);
if (H1 == H2)
l = mid;
else
r = mid - 1;
}
return l;
}

bool cmp(int a, int b)
{
int Q = lcp(a, b);
if (a + Q == st.size())
return true;
if (b + Q == st.size())
return false;
int val1 = maps[1][st[a + Q]-'a'];
int val2 = maps[2][st[b + Q]-'a'];
//    cout << val1 << "%%" << val2 << endl;
return val1 < val2;
}

int LL[N];
int sparse[N][20];

int Lcp(int a, int b)
{
if (a>b)
swap(a, b);
if (a == b)
return 1e9;
--b;
int q = 0;
while ((1 << q) * 2 < (b - a + 1))
++q;
return min(sparse[a][q], sparse[b - (1 << q) + 1][q]);
}

int main(){

ios_base::sync_with_stdio(0);
//cin.tie(0);

cin >> n >> tests;

pw[0] = 1;

for (int i = 1; i < N; i++)
{
pw[i] = pw[i - 1] * 173;
}

cin >> st;

for (int i = 0; i < 10; i++)
{
FE[st.size()][i] = st.size();
}
for (int i = st.size() - 1; i >= 0; --i)
{
for (int j = 0; j < 10; j++)
{
FE[i][j] = FE[i + 1][j];
if (st[i] == j + 'a')
FE[i][j] = i;
}
}

for (int i = 0; i < st.size(); i++)
{
for (int j = 0; j < 10; j++)
{
S[i + 1][j] = S[i][j];
if (st[i] == j + 'a')
S[i + 1][j] += pw[i];
}
}

for (int i = 0; i < st.size(); i++)
{
v.push_back(i);
}

sort(v.begin(), v.end(),cmp);

for (int i = 0; i < v.size(); i++)
{
whr[v[i]] = i;
}

for (int i = 0; i+1 < v.size(); i++)
{
LL[i] = lcp(v[i], v[i + 1]);
}

for (int lev = 0; lev < 17; lev++)
{
for (int i = 0; i < v.size(); i++)
{
if (lev == 0)
sparse[i][lev] = LL[i];
else
{
sparse[i][lev] = sparse[i][lev - 1];
if (i + (1 << lev) / 2 <= st.size())
sparse[i][lev] = min(sparse[i][lev],
 sparse[i + (1 << lev) / 2][lev - 1]);
}
}
}

for (int i = 1; i <= tests; i++)
{
int l, r;
cin >> l >> r;
--l;
--r;
int span = r - l + 1;
int ps = whr[l];
l = ps;
r = v.size() - 1;
while (l < r)
{
int mid = l + r+1;
mid /= 2;
if (Lcp(ps,mid) >= span)
l = mid;
else
r = mid - 1;
}
int R = r;
r = ps;
l = 0;
while (l < r)
{
int mid = l + r;
mid /= 2;
if (Lcp(ps,mid) >= span)
r = mid;
else
l = mid + 1;
}
cout << R-l+1 << endl;
}

cin.get(); cin.get();
return 0;
}









In   Java  :







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.HashMap;

public class Solution {

static class InputReader {

private InputStream stream;
private byte[] buf = new byte[4096];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}

public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}

void readCharArray(char[] ar, int len) {
for(int i=0; i<len; i++)
ar[i] = (char) read();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || 
c == '\r' || c == '\t' || c == -1;
}

public String next() {
return readString();
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}

static class OutputWriter {
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(
    new BufferedWriter(
        new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {

writer.print(objects[i]);
}
}

public void printLine(Object...objects) {
print(objects);
writer.println();
}

public void close() {
writer.close();
}

public void flush() {
writer.flush();
}

}

static class IOUtils {

public static int[] readIntArray(InputReader in,
 int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}

}

static final int MAX_CHARS = 'k'; 
static int LEN;
static char[] str;
static long[] mask;
static int[] lcp;
static HashMap<Long, ArrayList<Integer> > prefix_match;
public static void main(String[] args) {
OutputWriter writer = null;
try{
writer = new OutputWriter(System.out);
InputReader ri = new InputReader(System.in);

LEN = ri.readInt();
int q = ri.readInt();

str = new char[LEN];
ri.readCharArray(str, LEN);

prefix_match = new HashMap<>();

countPrefixMask();
createIsomorphicLCP();

// for each query
int l;
int r;
int count;
for(int i=0; i<q; i++){
l = ri.readInt()-1;
r = ri.readInt();
count = countIsomorphic(l, r);
writer.print(Integer.toString(count), '\n');
}

}catch(Exception ex){

} finally{
if(writer!=null){
//                writer.flush();
writer.close();
}
}
}

static int countIsomorphic(int pb, int pe){
if(pe-pb>=MASK_LEN)
return countIsomorphicShort(pb, pe); // simplified search for long strings
else
return countIsomorphicLong(pb, pe); // do full search 
}

static int countIsomorphicShort(int pb, int pe){
ArrayList<Integer> node = prefix_match.get(mask[pb]);
int m = pe-pb;
int count = 1; // always matched to itself
int last = LEN-m;
int j;
for(Integer ind : node){
j = ind; // unbox once

if(j==pb){ // always equals to self
continue;
}

if(j>last)
break; // skip items that are beyond range

if(countIsomorphicLength(j, pb, pe)==m){
count++;
}
}

return count;        
}


static int countIsomorphicLong(int pb, int pe){
int m = pe-pb;
int count = 1; // always matched to itself
boolean match = false;
int last = LEN-m;
for(int j=0; j<=last; j++){
if(j==pb){ // always equals to self
continue;
}

if(match){ // previous pattern matched
if(lcp[j-1]>=m){
count++;
continue;
}
}

if(!testMask(mask[pb], j, m)){
match = false;
continue;
}else if(m<=MASK_LEN){
count++;
continue;
}

if(countIsomorphicLength(j, pb, pe)==m){
count++;
match = true;
}else{
match = false;
}
}
return count;
}

static void createIsomorphicLCP(){
lcp = new int[LEN];

for(int i=0; i<LEN-1; i++){ 
lcp[i] = countIsomorphicLength(i, i+1, LEN);
while(lcp[i]>1){
lcp[i+1] = lcp[i++]-1;
}

}
}


static final int MASK_LEN = 16;
static final int MASK_SHIFT = 2; 
static void countPrefixMask(){
mask = new long[LEN]; // mask for each substring
long[] charmap = new long[MAX_CHARS];
long current; // next character counter
char ch;
long cur_mask;
for(int i=0; i<LEN; i++){ // for each substring
Arrays.fill(charmap, 0L);
current = 0L;
cur_mask = 0L; // accumulate mask
for(int j=0; j<MASK_LEN && j+i<LEN; j++){ 
ch=str[i+j];
if(charmap[ch]==0L){
charmap[ch] = ++current;
}
cur_mask |= charmap[ch]<<(j<<MASK_SHIFT);
}
mask[i] = cur_mask;
// add strings longer than MASK_LEN
if(LEN-i>=MASK_LEN){
// add current index to the list of matching prefix
ArrayList<Integer> node = prefix_match.get(cur_mask);
if(node==null){
node = new ArrayList<>();
prefix_match.put(cur_mask, node);
}
node.add(i);
}
}
}

static long filter;
static boolean testMask(long target, int index, int len){
if(MASK_LEN<=len){
return target == mask[index];
}
// if length of the request is less than mask
filter = -1L>>>( (MASK_LEN-len)<<MASK_SHIFT );
return (target & filter) == (mask[index] & filter );
}


static long countcalls = 0; 
static boolean[] mapped = new boolean[MAX_CHARS];
static char[] map = new char[MAX_CHARS];
static int countIsomorphicLength(int start, 
int pb, int pe){
countcalls++;

char c;
char p;
int comp_len = pe-pb;

Arrays.fill(mapped, false);
Arrays.fill(map, '\0');
for(int i=0; i<comp_len; i++){
c = str[start+i];
p = str[pb+i];
if(map[c]=='\0'){
if(mapped[p])
return i;

mapped[p] = true;

map[c] = p;
}else{
if(map[c]!=p)
return i;
}
}
return comp_len;
}

}












In   C  :






#include <stdio.h>
#include <malloc.h>
#define rint register int
typedef unsigned short ushort;
char* TVA;
char* S;
int n;
int cmpPos(const void*pa,const void*pb){
    rint a = *((ushort*)pa);
    rint b = *((ushort*)pb);
    int r = 1;
    if(a>b){
        r = a;
        a = b;
        b = r;
        r = -1;
    }    
    char* VA = TVA+ a*10;
    char* VB = TVA + b*10;
    for(;b<n;a++,b++){
        int dr = (int)VA[S[a]] - (int)VB[S[b]];
        if(dr) return dr*r;
    }
    return r;
}

inline int sameLen(int pa,int pb){
    rint a = pa;
    rint b = pb;
    if(a>b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
    pa = a;
    char* VA = TVA+a*10;
    char* VB = TVA+b*10;
    for(;b<n;a++,b++)
        if(VA[S[a]] != VB[S[b]]) return a - pa;
    return a-pa;
}

int main(void) {
    int q;
    scanf("%d %d",&n,&q);
    S = (char*)malloc(sizeof(char)*(n+1));
    scanf("%s",S);
    S[n] = -1;
    for(rint i=0;i<n;i++) S[i] -= 'a';
    TVA = (char*)malloc(sizeof(char)*(n+1)*10);
    for(rint i =0;i<10;i++) TVA[i+(n)*10] = i;
    for(rint i=n-1;i>=0;i--){
        char* TVAi = TVA + i*10;
        char sip = TVAi[S[i]+10];
        for(rint j=0;j<10;j++){
            if(TVAi[j+10] < sip) TVAi[j] = TVAi[j+10] + 1;
            else TVAi[j] = TVAi[j+10];
        }
        TVAi[S[i]] = 0;
    }
    ushort* SA = (ushort*)malloc(sizeof(ushort)*n);
    for(rint i=0;i<n;i++) SA[i] = (ushort)i;
    qsort(SA,n,sizeof(ushort),cmpPos);
    ushort* SB = (ushort*)malloc(sizeof(ushort)*n);
    ushort* KB = (ushort*)malloc(sizeof(ushort)*n);
    for(rint i=1;i<n;i++){
        SB[i] = sameLen(SA[i-1],SA[i]);
        KB[SA[i]] = i;
    }
    for(int w=0;w<q;w++){
        int x,y;
        scanf("%d %d",&x,&y);
        int d = y - x + 1;
        rint tx = KB[x-1];
        while(tx>0 && SB[tx]>=d) tx--;
        rint ty = KB[x-1]+1;
        while(ty<n && SB[ty]>=d) ty++;
        printf("%d\n",ty-tx);
    }
    return 0;
}









In   Python3  :








#! / bin / python3

import os
import sys

def calc_fingerprint (s):
    dict = {s [0]: 0}
    fingerprint = "0"
    j = 1
    for i in range (1, len (s)):
        if s [i] not in dict:
            dict [s [i]], j = j, j + 1
        fingerprint + = str (dict [s [i]])
    return int (fingerprint)

fingerprints = []
def naive_check (s, a, b):
    s1 = s [a-1: b]
    k = 0
    for i in range (len (s) - (ba)):
        if ba> 9 and fingerprints [a-1]! = fingerprints [i]:
            continue
        dict = {}
        s2 = s [i: i + (ba) +1]
        for i in range (b-a + 1):
            if s2 [i] not in dict:
                if s1 [i] in dict.values (): break
                dict [s2 [i]] = s1 [i]
            if dict [s2 [i]]! = s1 [i]: break
        else:
            k + = 1
    return k

n, q = map (int, input (). split ())
s = input ()

if len (s)> 10:
    for i in range (0, len (s) -10):
        fingerprints.append (calc_fingerprint (s [i: i + 10]))

for _ in range (q):
    a, b = folder (int, input (). rstrip (). split ())
    print (naive_check (s, a, b))

View More Similar Problems

Insert a Node at the head of a Linked List

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

View Solution →

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

View Solution →

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

View Solution →

Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

View Solution →

Reverse a linked list

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio

View Solution →

Compare two linked lists

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. If all data attributes are equal and the lists are the same length, return 1. Otherwise, return 0. Example: list1=1->2->3->Null list2=1->2->3->4->Null The two lists have equal data attributes for the first 3 nodes. list2 is longer, though, so the lis

View Solution →

Our Effort to provide you the best solutions requires some appreciation

Please disable your adblocker and refresh

Similar Strings

Problem Statement :

Solution :

View More Similar Problems

Insert a Node at the head of a Linked List

Insert a node at a specific position in a linked list

Delete a Node

Print in Reverse

Reverse a linked list

Compare two linked lists