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
Array Pairs
Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .
View Solution →Self Balancing Tree
An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ
View Solution →Array and simple queries
Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty
View Solution →Median Updates
The median M of numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median. Input: The first line is an integer, N , that indicates the number o
View Solution →Maximum Element
You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. Input Format The first line of input contains an integer, N . The next N lines each contain an above mentioned query. (It is guaranteed that each
View Solution →Balanced Brackets
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra
View Solution →