Cod sursa(job #3144344)

Utilizator DavidAA007Apostol David DavidAA007 Data 7 august 2023 14:55:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include<bits/stdc++.h>
//#define inf 0x3f3f3f3f
#define int long long
#define bit(x,i)(((x)>>(i))&1)
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod=1e9+7;
//typedef long long ll;
//const long long int mare=1LL*1000000000000000000;
const int mare=2e9+5;
const int nmax=1e6+5;
int T,n,m,i,j,t,suma,poz,ok,contor;
int x,y,c,st,dr,mij;
string a,b;
vector<int> ans;
int pi[nmax];
signed main() {
    FAST
    fin >> a;
    fin>> b;
    n = a.size()+1;
    m = b.size()+1;
    a = '#' + a;
    b = '#' + b;
    for (i = 2; i < n; i++) {
        while (t && a[t + 1] != a[i])
            t = pi[t];
        if (a[t + 1] == a[i])
            t++;
        pi[i] = t;
    }
    t = 0;
    for (i = 1; i < m; i++) {
        while (t && a[t + 1] != b[i])
            t = pi[t];
        if (a[t + 1] == b[i])
            t++;
        if (t == n - 1)
            ans.push_back(i - n + 1);
    }
    fout << ans.size() << "\n";
    for (i = 0; i < ans.size(); i++)
    {
        fout << ans[i] << " ";
        if(i==999)
            break;
    }
    return 0;
}

/*
 * vector<vector<int> > dp(n+1, vector<int> (m+1));
 */