Hi, I'm trying out a sample problem on strings wherein I take a string as input and find out the similarity of each of its suffix with itself.
For two strings A and B, the similarity of the strings is the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.
For example, if the input string is ababaa. Then its suffixes would be ababaa, babaa, abaa, baa, aa, a. The corresponding similarities would be 6, 0, 3, 0, 1, 1. These are added and printed on the console.
Now in my problem, I'm taking input as follows. First line is the number of strings whose sum of similarities (with each of it's suffixes) have to be printed. In the next lines, I enter that many number of strings. I have written code for the problem and it is running fine for normal inputs. But when i give a very large string, it is giving the following runtime exception message "Could not allocate 8192 bytes". My code is as follows
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static List<int> listOfSimilarities = new List<int>();
static void Main(String[] args) {
int t = 0;
t = Convert.ToInt32(Console.ReadLine());
if( t >= 1 && t <=10)
{
List<string> listOfStrings = new List<string>();
string input = string.Empty;
for(int i = 1 ; i <= t ; i++)
{
input = Console.ReadLine().ToString();
if(input.Length < 100000)
{
listOfStrings.Add(input);
}
}
foreach(string str in listOfStrings)
{
List<string> listOfSuffixes = new List<string>();
listOfSuffixes = GetSuffixes(str);
List<int> listOfSimilaritiesForEachSuffix = new List<int>();
listOfSimilaritiesForEachSuffix = GetSimilaritiesWithString(str, listOfSuffixes);
int sumOfSimilarities = GetSumOfSimilarities(listOfSimilaritiesForEachSuffix);
listOfSimilarities.Add(sumOfSimilarities);
}
foreach(int similarity in listOfSimilarities)
{
Console.Write(similarity + "\n");
}
}
}
static int GetSumOfSimilarities(List<int> listOfSimilaritiesForEachSuffix)
{
int result = 0;
foreach(int i in listOfSimilaritiesForEachSuffix)
{
result += i;
}
return result;
}
static List<int> GetSimilaritiesWithString(string str, List<string> listOfSuffixes)
{
List<int> listOfSimilaritiesForEachSuffix = new List<int>();
char[] arrayOfActualString = str.ToCharArray();
foreach(string suffix in listOfSuffixes)
{
int count = 0;
char[] suffixArray = suffix.ToCharArray();
for(int i = 0; i < suffixArray.GetLength(0) ; i++)
{
if(suffixArray[i] == arrayOfActualString[i])
{
count++;
}
else
{
break;
}
}
listOfSimilaritiesForEachSuffix.Add(count);
}
return listOfSimilaritiesForEachSuffix;
}
static List<string> GetSuffixes(string str)
{
List<string> listOfSuffixes = new List<string>();
for(int i = 0; i < str.Length ; i++)
{
listOfSuffixes.Add(str.Substring(i));
}
return listOfSuffixes;
}
}
Any idea as to why this is happening?