Cod sursa(job #2408427)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 17 aprilie 2019 22:40:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "strmatch";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 2000006;

string v, r;
int pred[nmax];

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> v >> r; v += "#";
    pred[0] = -1;
    for (int i = 1; i < v.length()-1; ++i){
        int now = pred[i-1];
        while(now != -1 && v[now+1] != v[i])
            now = pred[now];
        if(v[now+1] == v[i])
            ++now;
        pred[i] = now;
    }
    int now = -1, sol = 0;;
    vector<int> ans;
    for (int i = 0; i < r.length(); ++i){
        while(now != -1 && v[now+1] != r[i])
            now = pred[now];
        if(v[now+1] == r[i])
            ++now;
        if(now == v.length()-2){
            ++sol;
            if(sol <= 1000)
                ans.push_back(i-now);
        }
    }
    fout << sol << "\n";
    for (auto x : ans)
        fout << x << " ";
    return 0;
}