Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Implemented FFT convolution and lazy segment tree — fast and efficient#1848

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
jsjgdh wants to merge1 commit intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromjsjgdh:my-new-branch
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
152 changes: 152 additions & 0 deletionsMaths/FFT.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
// Cooley–Tukey FFT (radix-2, iterative) and polynomial/big-integer multiplication
// Exports: fft, ifft, multiplyPolynomials, convolveReal, multiplyBigIntegers

function isPowerOfTwo(n) {
return n && (n & (n - 1)) === 0
}

function nextPowerOfTwo(n) {
let p = 1
while (p < n) p <<= 1
return p
}

function bitReverse(n, bits) {
let rev = 0
for (let i = 0; i < bits; i++) {
rev = (rev << 1) | (n & 1)
n >>= 1
}
return rev
}

function fft(re, im, invert = false) {
const n = re.length
if (!isPowerOfTwo(n)) {
throw new Error('fft input length must be a power of two')
}
if (im.length !== n) throw new Error('re and im lengths must match')

// Bit-reverse permutation
const bits = Math.floor(Math.log2(n))
for (let i = 0; i < n; i++) {
const j = bitReverse(i, bits)
if (i < j) {
;[re[i], re[j]] = [re[j], re[i]]
;[im[i], im[j]] = [im[j], im[i]]
}
}

// Iterative FFT
for (let len = 2; len <= n; len <<= 1) {
const ang = 2 * Math.PI / len * (invert ? 1 : -1)
const wLenRe = Math.cos(ang)
const wLenIm = Math.sin(ang)

for (let i = 0; i < n; i += len) {
let wRe = 1
let wIm = 0
for (let j = 0; j < len / 2; j++) {
const uRe = re[i + j]

Check failure on line 50 in Maths/FFT.js

View workflow job for this annotation

GitHub Actions/ Check for spelling errors

uRe ==> sure, ire, are, urea, rue
const uIm = im[i + j]
const vRe = re[i + j + len / 2]
const vIm = im[i + j + len / 2]

// v * w
const tRe = vRe * wRe - vIm * wIm

Check failure on line 56 in Maths/FFT.js

View workflow job for this annotation

GitHub Actions/ Check for spelling errors

tRe ==> tree, the
const tIm = vRe * wIm + vIm * wRe

// butterfly
re[i + j] = uRe + tRe

Check failure on line 60 in Maths/FFT.js

View workflow job for this annotation

GitHub Actions/ Check for spelling errors

tRe ==> tree, the

Check failure on line 60 in Maths/FFT.js

View workflow job for this annotation

GitHub Actions/ Check for spelling errors

uRe ==> sure, ire, are, urea, rue
im[i + j] = uIm + tIm
re[i + j + len / 2] = uRe - tRe

Check failure on line 62 in Maths/FFT.js

View workflow job for this annotation

GitHub Actions/ Check for spelling errors

tRe ==> tree, the

Check failure on line 62 in Maths/FFT.js

View workflow job for this annotation

GitHub Actions/ Check for spelling errors

uRe ==> sure, ire, are, urea, rue
im[i + j + len / 2] = uIm - tIm

// w *= wLen
const nwRe = wRe * wLenRe - wIm * wLenIm
const nwIm = wRe * wLenIm + wIm * wLenRe
wRe = nwRe
wIm = nwIm
}
}
}

if (invert) {
for (let i = 0; i < n; i++) {
re[i] /= n
im[i] /= n
}
}
}

function ifft(re, im) {
fft(re, im, true)
}

function convolveReal(a, b) {
const need = a.length + b.length - 1
const n = nextPowerOfTwo(need)

const reA = new Array(n).fill(0)
const imA = new Array(n).fill(0)
const reB = new Array(n).fill(0)
const imB = new Array(n).fill(0)

for (let i = 0; i < a.length; i++) reA[i] = a[i]
for (let i = 0; i < b.length; i++) reB[i] = b[i]

fft(reA, imA)
fft(reB, imB)

const re = new Array(n)
const im = new Array(n)
for (let i = 0; i < n; i++) {
// (reA + i imA) * (reB + i imB)
re[i] = reA[i] * reB[i] - imA[i] * imB[i]
im[i] = reA[i] * imB[i] + imA[i] * reB[i]
}

ifft(re, im)

const res = new Array(need)
for (let i = 0; i < need; i++) {
res[i] = Math.round(re[i]) // round to nearest integer to counter FP errors
}
return res
}

function multiplyPolynomials(a, b) {
return convolveReal(a, b)
}

function trimLSD(arr) {
// Remove trailing zeros in LSD-first arrays
let i = arr.length - 1
while (i > 0 && arr[i] === 0) i--
return arr.slice(0, i + 1)
}

function multiplyBigIntegers(A, B, base = 10) {
// A, B are LSD-first arrays of digits in given base
if (!Array.isArray(A) || !Array.isArray(B)) {
throw new Error('Inputs must be digit arrays')
}
const conv = convolveReal(A, B)

// Carry handling
const res = conv.slice()
let carry = 0
for (let i = 0; i < res.length; i++) {
const total = res[i] + carry
res[i] = total % base
carry = Math.floor(total / base)
}
while (carry > 0) {
res.push(carry % base)
carry = Math.floor(carry / base)
}
const trimmed = trimLSD(res)
return trimmed.length === 0 ? [0] : trimmed
}

export { fft, ifft, convolveReal, multiplyPolynomials, multiplyBigIntegers }
59 changes: 59 additions & 0 deletionsMaths/test/FFT.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
import { multiplyPolynomials, multiplyBigIntegers, convolveReal } from '../FFT'

describe('FFT polynomial multiplication', () => {
it('multiplies small polynomials', () => {
const a = [1, 2, 3] // 1 + 2x + 3x^2
const b = [4, 5] // 4 + 5x
expect(multiplyPolynomials(a, b)).toEqual([4, 13, 22, 15])
})

it('convolution matches naive for random arrays', () => {
const a = [0, 1, 0, 2, 3]
const b = [1, 2, 3]
const conv = convolveReal(a, b)
const naive = []
for (let i = 0; i < a.length + b.length - 1; i++) {
let sum = 0
for (let j = 0; j < a.length; j++) {
const k = i - j
if (k >= 0 && k < b.length) sum += a[j] * b[k]
}
naive.push(sum)
}
expect(conv).toEqual(naive)
})
})

describe('FFT big integer multiplication', () => {
function digitsToBigInt(digs, base = 10) {
// LSD-first digits to BigInt
let s = ''
for (let i = digs.length - 1; i >= 0; i--) s += digs[i].toString(base)
return BigInt(s)
}

function bigIntToDigits(n, base = 10) {
if (n === 0n) return [0]
const digs = []
const b = BigInt(base)
let x = n
while (x > 0n) {
digs.push(Number(x % b))
x /= b
}
return digs
}

it('multiplies large integer arrays (base 10)', () => {
const A = Array.from({ length: 50 }, () => Math.floor(Math.random() * 10))
const B = Array.from({ length: 50 }, () => Math.floor(Math.random() * 10))
const prodDigits = multiplyBigIntegers(A, B, 10)
const prodBigInt = digitsToBigInt(A) * digitsToBigInt(B)
expect(prodDigits).toEqual(bigIntToDigits(prodBigInt))
})

it('handles leading zeros and zero cases', () => {
expect(multiplyBigIntegers([0], [0])).toEqual([0])
expect(multiplyBigIntegers([0, 0, 1], [0, 2])).toEqual([0, 0, 0, 2])
})
})
102 changes: 102 additions & 0 deletionsString/SuffixAutomaton.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
// Suffix Automaton implementation for substring queries
// Provides: buildSuffixAutomaton, countDistinctSubstrings, longestCommonSubstring

class SAMState {
constructor() {
this.next = Object.create(null)
this.link = -1
this.len = 0
}
}

function buildSuffixAutomaton(s) {
const states = [new SAMState()]
let last = 0

for (const ch of s) {
const cur = states.length
states.push(new SAMState())
states[cur].len = states[last].len + 1

let p = last
while (p !== -1 && states[p].next[ch] === undefined) {
states[p].next[ch] = cur
p = states[p].link
}

if (p === -1) {
states[cur].link = 0
} else {
const q = states[p].next[ch]
if (states[p].len + 1 === states[q].len) {
states[cur].link = q
} else {
const clone = states.length
states.push(new SAMState())
states[clone].len = states[p].len + 1
states[clone].next = { ...states[q].next }
states[clone].link = states[q].link

while (p !== -1 && states[p].next[ch] === q) {
states[p].next[ch] = clone
p = states[p].link
}
states[q].link = states[cur].link = clone
}
}

last = cur
}

return { states, last }
}

function countDistinctSubstrings(s) {
const { states } = buildSuffixAutomaton(s)
let count = 0
// State 0 is the initial state; skip it in the sum
for (let v = 1; v < states.length; v++) {
const link = states[v].link
const add = states[v].len - (link === -1 ? 0 : states[link].len)
count += add
}
return count
}

function longestCommonSubstring(a, b) {
// Build SAM of string a, then walk b to find LCS
const { states } = buildSuffixAutomaton(a)
let v = 0
let l = 0
let best = 0
let bestEnd = -1

for (let i = 0; i < b.length; i++) {
const ch = b[i]
if (states[v].next[ch] !== undefined) {
v = states[v].next[ch]
l++
} else {
while (v !== -1 && states[v].next[ch] === undefined) {
v = states[v].link
}
if (v === -1) {
v = 0
l = 0
continue
} else {
l = states[v].len + 1
v = states[v].next[ch]
}
}
if (l > best) {
best = l
bestEnd = i
}
}

if (best === 0) return ''
return b.slice(bestEnd - best + 1, bestEnd + 1)
}

export { buildSuffixAutomaton, countDistinctSubstrings, longestCommonSubstring }
24 changes: 24 additions & 0 deletionsString/test/SuffixAutomaton.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
import { countDistinctSubstrings, longestCommonSubstring } from '../SuffixAutomaton'

describe('Suffix Automaton - distinct substrings', () => {
it('handles empty string', () => {
expect(countDistinctSubstrings('')).toBe(0)
})

it('counts distinct substrings correctly', () => {
expect(countDistinctSubstrings('aaa')).toBe(3)
expect(countDistinctSubstrings('abc')).toBe(6)
expect(countDistinctSubstrings('ababa')).toBe(9)
})
})

describe('Suffix Automaton - longest common substring', () => {
it('finds LCS of two strings', () => {
expect(longestCommonSubstring('xabcdxyz', 'xyzabcd')).toBe('abcd')
expect(longestCommonSubstring('hello', 'yellow')).toBe('ello')
})

it('returns empty when no common substring', () => {
expect(longestCommonSubstring('abc', 'def')).toBe('')
})
})
Loading
Loading
[8]ページ先頭
©2009-2025 Movatter.jp