|
|
|
|
|
|
|
Вернуться
| 1 Терентьев Михал Палыч, 23 сентября 2024 г. 11:45:52 | |
|
Заменил на ваш ввод, дошло до 11 теста (MLE 11)
|
|
|
| 2 Терентьев Михал Палыч, 23 сентября 2024 г. 11:36:50 | |
|
Конкретно этот код выдает другое. Проверяйте onlinegdb.com/DfFo5t75t .
|
|
|
| 3 Панкин Александр Сергеевич, 23 сентября 2024 г. 11:35:58 | |
Проблемма была в чтении файла. Позможно из за символа переноса троки. Изменил чтение с
in, _ := os.Open("input.txt")
out, _ := os.Create("output.txt")
var str string
var pattern string
fmt.Fscanf(in, "%s", &str)
fmt.Fscanf(in, "%s", &pattern)
на
in, _ := os.Open("input (1).txt")
out, _ := os.Create("output.txt")
var str string
var pattern string
scanner := bufio.NewScanner(in)
scanner.Scan()
str = scanner.Text()
scanner.Scan()
pattern = scanner.Text()
Заработало
|
|
|
| 4 Панкин Александр Сергеевич, 22 сентября 2024 г. 23:27:00 | |
|
Сейчас тоже проверил этот код в onlinegdb вывело 0 5 7 такой ответ проходит первый тест
|
|
|
| 5 Терентьев Михал Палыч, 22 сентября 2024 г. 21:41:58 | |
|
Это код, который вы отправили на проверку? Проверил в onlinegdb, вывело совсем другое. А вообще, посмотрите уже имеющийся псевдокод, например, на neerc. ifmo. ru.
|
|
|
| 6 Панкин Александр Сергеевич, 22 сентября 2024 г. 19:36:33 | |
}
}
return out
}
func main() {
in, _ := os.Open("input.txt")
out, _ := os.Create("output.txt")
var str string
var pattern string
fmt.Fscanf(in, "%s", &str)
fmt.Fscanf(in, "%s", &pattern)
fmt.Fprintf(out, "%s", SearchForASubstring(str, pattern))
}
//endregion
|
|
|
| 7 Панкин Александр Сергеевич, 22 сентября 2024 г. 19:35:29 | |
package main
import (
"fmt"
"os"
"strconv"
)
//func KMP(s string) []int {
// var n = len(s)
//
// var pi = make([]int, n)
//
// for i := 1; i < n; i++ {
// var j = pi[i-1]
//
// for j > 0 && s[i] != s[j] {
// j = pi[j-1]
// }
//
// if s[i] == s[j] {
// j++
// }
//
// pi[i] = j
// }
//
// return pi
//}
//
//func RepeatedSubstringPattern(s string) bool {
// var pi = KMP(s)
//
// if pi[len(s)-1] != 0 && len(s)%(len(s)-pi[len(s)-1]) == 0 {
// return true
// } else {
// return false
// }
//}
//
//func main() {
// fmt.Println(RepeatedSubstringPattern("abac"))
//}
// region ACMP
func KMP(s string) []int {
var n = len(s)
var pi = make([]int, n)
for i := 1; i < n; i++ {
var j = pi[i-1]
for j > 0 && s[i] != s[j] {
j = pi[j-1]
}
if s[i] == s[j] {
j++
}
pi[i] = j
}
return pi
}
func KmpAuto(s string, startASCII uint8, endASCII uint8) [][]int {
s += string([]uint8{startASCII - 1})
var al = endASCII - startASCII + 1
var n = len(s)
var pi = KMP(s)
var out [][]int = make([][]int, n)
for i := 0; i < n; i++ {
out[i] = make([]int, al)
for c := uint8(0); c < al; c++ {
if i > 0 && (c+startASCII) != s[i] {
out[i][c] = out[pi[i-1]][c]
} else {
var add int
if (c + startASCII) == s[i] {
add = 1
}
out[i][c] = i + add
}
}
}
return out
}
func SearchForASubstring(str string, pattern string) string {
var out = ""
var aut = KmpAuto(pattern, 97, 122)
var curr = 0
for i, c := range str {
curr = aut[curr][c-97]
if curr == len(pattern) {
out += strconv.FormatInt(int64(i-len(pattern)+1), 10) + " "
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
