Cod sursa(job #2457989)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 19 septembrie 2019 11:25:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

const int NMAX = 2000005;
int phi[2*NMAX];
vector<int>sol;
string s , s1;

void KermitManancaPrune(string s)
{
    phi[0] = -1;
    for(int i = 1 ; i < s.size() ; i++)
    {
        int x = i-1;
        while(s[phi[x]+1] != s[i] && phi[x]!=-1)
            x = phi[x];
        if(s[phi[x]+1] == s[i])
            phi[i] = phi[x]+1;
        else
            phi[i] = -1;
    }
}

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> s1 >> s;
    s = (s1+"*"+s);
    KermitManancaPrune(s);
    for(int i = s1.size()+1 ; i < s.size() ; i++)
    {
        if(phi[i] == s1.size()-1)
            {
                sol.push_back(i-s1.size()-s1.size());
            }
    }
    cout << sol.size() << "\n";
    int t = sol.size();
    int jfc = min(1000,t);
    for(int i = 0 ; i < jfc ; i++)
        cout << sol[i] << " ";
    return 0;
}