Submission 1074 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1074	20/05/2013 12:40:40	agarwaen	E - EString	Accepted	78	22.4 KiB	GNU G++ 5.1.0

Code

#include <iostream>
#include <cstring>
using namespace std;

#define FOR(i,n) for (int i = 1; i <= (n); ++i)
#define REP(i,n) for (int i = 0; i < (n); ++i)

#define DB(x) cout << #x << " = " << x << endl;

const int MAX = 1000009;

int N;
int prab[2*MAX], zba[2*MAX];
char a[MAX], b[MAX], ba[2*MAX], rab[2*MAX];

void prefix(const char s[MAX], int p[MAX])
{
	int n = strlen(s+1);
	for (int i = 2, j = 0; i <= n; ++i)
	{
		while (j && s[j+1] != s[i]) j = p[j];
		if (s[j+1] == s[i]) ++j;
		p[i] = j;
	}
}

void calc_z(char *s, int *z)
{
	int N = strlen(s);
	z[0] = 0;

int l = 0, r = 0;
	for (int i = 1; i < N; ++i)
	{
		if (i > r)
		{
			int j;
			for (j = 0; i+j < N && s[i+j] == s[j]; ++j);
			z[i] = j;
			l = i;
			r = i + j - 1;
		}
		else
		{
			if (z[i-l] < r - i + 1)
				z[i] = z[i-l];
			else
			{
				int j;
				for (j = 1; r+j < N && s[r+j] == s[r-i+j]; j++);
				z[i] = r - i + j;
				l = i;
				r = r + j - 1;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);

cin.getline(a+1, MAX);
	cin.getline(b+1, MAX);

if ((N = strlen(a+1)) != strlen(b+1))
	{
		cout << "-1 -1" << endl;
		return 0;
	}

FOR(i, N) rab[i] = a[N-i+1];
	rab[N+1] = 127;
	FOR(i, N) rab[N+1+i] = b[i];
	prefix(rab, prab);

FOR(i, N) ba[i] = b[i];
	ba[N+1] = 127;
	FOR(i, N) ba[N+1+i] = a[i];
	calc_z(ba+1, zba+1);

int ai = -1, aj = -1;
	for (int i = 1; i < N; ++i)
	{
		if (a[i] != b[N-i+1]) break;

int j = N - prab[2*N+1-i] + 1;

if (j > i && zba[N+1+i+1] >= j-i-1)
		{
			ai = i-1; aj = j-1;
		}
	}

cout << ai << ' ' << aj << endl;

return 0;
}// UH++

Judgement Details

Test 01: 0.009 0.000 1440K ok
Test 02: 0.008 0.000 1440K ok
Test 03: 0.148 0.078 22924K ok
Test 04: 0.009 0.000 1408K ok
Test 05: 0.008 0.016 1424K ok
Test 06: 0.008 0.000 1408K ok
Test 07: 0.009 0.000 1444K ok
Test 08: 0.007 0.000 1444K ok
Test 09: 0.007 0.000 1444K ok
Test 10: 0.008 0.000 1444K ok
Test 11: 0.008 0.000 1444K ok
Test 12: 0.008 0.000 1440K ok
Test 13: 0.009 0.000 1444K ok
Test 14: 0.009 0.000 1444K ok
Test 15: 0.008 0.000 1440K ok
Test 16: 0.008 0.000 1464K ok
Test 17: 0.008 0.000 1444K ok
Test 18: 0.013 0.000 1464K ok
Test 19: 0.011 0.000 1444K ok
Test 20: 0.008 0.000 1408K ok
Test 21: 0.012 0.000 1440K ok
Test 22: 0.013 0.000 1404K ok
Test 23: 0.065 0.000 1444K ok
Test 24: 0.011 0.000 1444K ok
Test 25: 0.014 0.016 1408K ok
Test 26: 0.010 0.000 1408K ok
Test 27: 0.127 0.062 22920K ok
Test 28: 0.113 0.078 22924K ok
Test 29: 0.100 0.078 22924K ok
Accepted

Matcom Online Grader Faculty of Mathematics and Computer Science of University of Havana

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana