There was a competition here http://www.codechef.com/MARCH14
and there was a problem A story with strings
I solved it and want to know if it is successful
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Hash
{
string s;
int H;
};
int main()
{
string s1, s2;
getline(cin, s1);
getline(cin, s2);
vector<Hash> H1(s1.size() * s1.size());
vector<Hash> H2(s2.size() * s2.size());
int k1 = 0;
int k2 = 0;
for(int i = 0; i < s1.size(); ++i)
{
int HforH1 = s1[i];
H1[k1].H = s1[i];
H1[k1].s = s1[i];
++k1;
for(int j = i + 1; j < s1.size(); ++j)
{
HforH1 += s1[j] * 19 + s1[j - 1];
H1[k1].H = HforH1;
H1[k1].s = s1.substr(i, j - i + 1);
++k1;
}
}
for(int i = 0; i < s2.size(); ++i)
{
int HforH2 = s2[i];
H2[k2].H = s2[i];
H2[k2].s = s2[i];
++k2;
for(int j = i + 1; j < s2.size(); ++j)
{
HforH2 += s2[j] * 19 + s2[j - 1];
H2[k2].H = HforH2;
H2[k2].s = s2.substr(i, j - i + 1);
++k2;
}
}
Hash maxOf2;
maxOf2.H = H1[0].H;
maxOf2.s = H1[0].s;
for(int i = 0; i < H1.size(); ++i)
for(int j = 0; j < H2.size(); ++j)
{
if(H1[i].H == H2[j].H)
{
if(H1[i].H > maxOf2.H)
{
maxOf2.H = H1[i].H;
maxOf2.s = H1[i].s;
}
}
}
cout << maxOf2.s.size() << endl << maxOf2.s << endl;
}
this is the solution for getline(cin, string)