Algorithm
Problem Name: beecrowd | 2126
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2126
Searching Subsequences
By Igor Gomes, UEVA 
Brazil
Timelimit: 1
Given two natural numbers N1 and N2, it is said that N1 is contiguous subsequence of N2 if in N1 appear all digits in the same order and contiguously. Create an program that reads two natural numbers and write if the first is a contiguous subsequence of the second.
Input
The input consists of several test cases and ends with the end of file (EOF). The first line of each entry is composed of anatural value N1 (1 <N1 <1010), the second line is composed of a value N2 (N1 <N2<1032).
Output
For each test case print the amount of contiguous subsequences and the position where the substring starts, if there is more of a subsequence, print where it started the last substring. If no there subsequence, print "Nao existe subsequencia" (that means no there subsequence). Show the result as the sample output.
| Input Sample | Output Sample |
|
78954 |
Caso #1: Caso #2: Caso #3: |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int main(){
int i=0,j=0,k=0,l=0,p=0,y;
string a,b;
while(cin >> a >> b ){
k++;
l = j = p = 0;
int t = 0;
for(i = 0; i < b.size(); i++){
if(b[i] == a[j] || b[i] == a[0]){
if(b[i] == b[i-1] && j!=0)
j = 1;
else{
j++;
t++;
}
//if(j == a.size()-1) {
// if(l > 0)
// p = p+1;
// else
p = i+1;
// }
}else{
j=0;
t=0;
}
if(t==a.size()){
l++;
//cout << p << endl;
y = (p-t)+1;
t = 0;j=0;
}
}
if(l!=0){
printf("Caso #%d:\nQtd.Subsequencias: %d\nPos: %d\n",k,l,y);
}else{
printf("Caso #%d:\nNao existe subsequencia\n",k);
}
cout << endl;
}
return 0;
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
for (let i = 0, j = 1; lines[i]; i += 2) {
const sub = lines[i];
const str = lines[i + 1];
const reg = new RegExp(`${sub}`, 'g');
const response = str.match(reg);
if (!response) {
console.log(`Caso #${j++}:`);
console.log(`Nao existe subsequencia`);
console.log(``)
} else {
console.log(`Caso #${j++}:`);
console.log(`Qtd.Subsequencias: ${response.length}`);
console.log(`Pos: ${str.lastIndexOf(response[0]) + 1}`);
console.log(``)
}
}
Input
#3 Code Example with Python Programming
Code -
Python Programming
caso = 1
while True:
try:
n1 = input()
n2 = input()
print('Caso #%d:' % caso)
qt = n2.count(n1)
if qt == 0:
print('Nao existe subsequencia')
else:
print('Qtd.Subsequencias: %d' % qt)
qt = n2.rfind(n1)
print('Pos: %d' % (int(qt)+1))
print()
caso += 1
except EOFError:
break
Input