Cod sursa(job #2480836)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 26 octombrie 2019 10:34:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int the = 2000000;
const int bath = 41;
const int thebath = the+bath;

string a, b;
int c[thebath];

void readitup(){
    a.reserve(thebath), b.reserve(thebath);
    fin >> a >> b;
    a.insert(a.begin(), ' ');
    b.insert(b.begin(), ' ');
}

void preprocessit(){
    int x = 0;
    for(int i = 2; i < a.size(); i++){
        while(a[i] != a[x+1] && x > 0){
            x = c[x];
        }
        if(a[i] == a[x+1]){
            x++;
        }
        c[i] = x;
    }
}

int solol = 0;
vector<int> sol;
void findit(){
    int x = 0;
    for(int i = 1; i < b.size(); i++){
        while(a[x+1] != b[i] && x > 0){
            x = c[x];
        }
        if(a[x+1] == b[i]){
            x++;
        }
        if(x == a.size()-1){
            solol++;
            if(solol < 1000){
                sol.push_back(i-a.size()+1);
            }
        }
    }
}

int main()
{
    readitup();
    preprocessit();
    findit();
    fout << solol << "\n";
    for(auto a : sol){
        fout << a << " ";
    }
    return 0;
}