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 →