Submission #298453

#	Time	Username	Problem	Language	Result	Execution time	Memory
298453		peuch	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	17 ms	384 KiB

necklace

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 410;

char st1[MAXN];
char st2[MAXN];

int prefix[MAXN];
int sufix[MAXN];

int ans;
pair<int, int> pos;

int n1, n2;

int main(){
	scanf(" %s", st1);
	scanf(" %s", st2);
	n1 = strlen(st1);
	n2 = strlen(st2);
	for(int i = 0; i < n1; i++){
		for(int j = 1; j < n1; j++)
			swap(st1[j - 1], st1[j]);

		for(int j = 0; j < n2; j++){
			prefix[j] = 0;
			sufix[j] = 0;
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[k] == st2[(j + k) % n2]) prefix[j]++;
				else break;
			}
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[n1 - k - 1] == st2[(j - k + n2) % n2]) sufix[j]++;
				else break;
			}
		}

		// printf("%s\n", st1);
		// printf("%s\n", st2);
		for(int j = 0; j < n2; j++){
			for(int k = (j + prefix[j]) % n2; k != j; k++, k %= n2){
				int aux = (k - j + n2) % n2 + 1;
				if(prefix[j] + sufix[k] >= aux) ans = max(ans, min(aux, min(n1, n2)));
			}
			// printf("\tp[%d] = %d, s[%d] = %d\n", j, prefix[j], j, sufix[j]);
		}
	}

	reverse(st2, st2 + n2);

	for(int i = 0; i < n1; i++){
		for(int j = 1; j < n1; j++)
			swap(st1[j - 1], st1[j]);

		for(int j = 0; j < n2; j++){
			prefix[j] = 0;
			sufix[j] = 0;
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[k] == st2[(j + k) % n2]) prefix[j]++;
				else break;
			}
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[n1 - k - 1] == st2[(j - k + n2) % n2]) sufix[j]++;
				else break;
			}
		}

		// printf("%s\n", st1);
		// printf("%s\n", st2);
		for(int j = 0; j < n2; j++){
			for(int k = (j + prefix[j]) % n2; k != j; k++, k %= n2){
				int aux = (k - j + n2) % n2 + 1;
				if(prefix[j] + sufix[k] >= aux) ans = max(ans, min(aux, min(n1, n2)));
			}
			// printf("\tp[%d] = %d, s[%d] = %d\n", j, prefix[j], j, sufix[j]);
		}
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  scanf(" %s", st1);
      |  ~~~~~^~~~~~~~~~~~
necklace.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf(" %s", st2);
      |  ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40