Cod sursa(job #3254097)

Utilizator gBneFlavius Andronic gBne Data 6 noiembrie 2024 09:13:43
Problema Potrivirea sirurilor Scor 6
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <iostream>
#include <string>
#include <queue>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int poz[2000005], sol[2000005];
queue<int> out;

void kmp(string& s){
    poz[0] = 0;
    int j = 0;
    for(int i = 1; i < s.size(); ++ i){
        if(s[i] == s[j]){
            poz[i] = j;
            ++ j;
        }
        else{
            while(s[i] != s[j] && j != 0){
                j = s[j];
            }
            poz[i] = j;
            ++ j;
        }
    }
}

void solve(string& s, string& p){
    int j = 0, ans = 0;
    for(int i = 0; i < s.size(); ++ i){
        if(s[i] == p[j]){
            sol[i] = j;
            ++ j;
        }
        else{
            while(s[i] != p[j] && j != 0){
                j = poz[j];
            }
            sol[i] = j;
            ++ j;
        }
        if(j == p.size()){
            ++ ans;
            if(ans <= 1000){
                out.push(i - p.size() + 1);
            }
            -- j;
            j = poz[j];
            while(s[i] != p[j] && j != 0){
                j = poz[j];
            }
            ++ j;
        }
    }
    fout << ans << '\n';
    while(!out.empty()){
        fout << out.front() << ' ';
        out.pop();
    }
}

int main()
{
    string s1, s2;
    fin >> s1 >> s2;
    kmp(s1);
    solve(s2, s1);
    return 0;
}