CSES 1753 ↗

String Matching

Number of positions where the pattern occurs in the string.

13
submissions
0.892
best score

Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.

Input

The first input line has a string of length n, and the second input line has a pattern of length m. Both of them consist of characters a–z.

Output

Print one integer: the number of occurrences.

Constraints

  • 1≤n,m≤106

Example

Input:

saippuakauppias
pp

Output:

2

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/StringMatching/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
308,734,43296,991,764,894

13 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

13 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.892308,734,432talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-23 02:56 UTC
2lukerj000.879382,418,710talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-21 22:55 UTC
3lukerj000.86496,991,764,894talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-23 22:35 UTC
4lukerj000.830473,983,781talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-22 23:23 UTC
5lukerj000.817481,119,368talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 23:09 UTC
6lukerj000.813422,707,999talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-23 23:38 UTC
7lukerj000.766560,156,644talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-21 22:45 UTC
8lukerj000.716582,145,395talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-24 04:57 UTC
9lukerj000.695807,368,550talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 19:46 UTC
10lukerj000.693819,449,400talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 00:14 UTC
11lukerj000.690827,622,722talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-21 20:46 UTC
12lukerj000.686858,862,198talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 21:13 UTC
13lukerj000.680855,753,671talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 04:04 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.