Cod sursa(job #2372426)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 7 martie 2019 09:14:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 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;

int n, m, prv[2000005];
string s1, s2;

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> s1 >> s2;
    n = s1.length(), m = s2.length();
    prv[0] = 0;
    int k = 0;
    for (int i = 1; i < n; ++i){
        while(k > 0 && s1[k] != s1[i])
            k = prv[k-1];
        if(s1[k] == s1[i])
            ++k;
        prv[i] = k;
    }
    int sol = 0;
    vector<int> ans;
    k = 0;
    for (int i = 0; i < m; ++i){
        while(k > 0 && s1[k] != s2[i])
            k = prv[k-1];
        if(s1[k] == s2[i])
            ++k;
        if(k == n){
            ++sol;
            if(sol <= 1000)
                ans.push_back(i-n+1);

        }
    }
    fout << sol << "\n";
    for (auto x : ans)
        fout << x << " ";
    fout << "\n";
    return 0;
}