Cod sursa(job #2782831)

Utilizator alien14Razvan alien14 Data 13 octombrie 2021 10:35:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s) 
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s) 
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x)) 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pl; 
typedef vector<int> vi; 
typedef vector<ll> vl; 
#define modulo 1000000007
#define FOR(i,a,b) for(int i=a;i<=b;i++)
typedef vector<pii> vpii;
#define dim 2000005
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[dim],b[dim];
int v[1001],p[dim];
int k,t;

int main() 
{
    ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
    fin>>a;
    fin>>b;
    int n = strlen(a);
    int m = strlen(b);
    for(int i = 2;i<n;i++)
    {
        while(k && a[k+1] != a[i])
            k = p[k];
        if(a[k+1] == a[k])
            k++;
        p[i] = k;
    }
    int i;
    for(k = 0,i=1;i<m;i++) 
    {
        while(k && a[k+1] != b[i])
            k=p[k];
        if(a[k+1] == b[i])
            k++;
        if(k == n-1 && a[0] == b[i-k])
        {
            if(t < 1000)
                v[t] = i-n+1;
            t++;
        }
    }
    fout<<t<<'\n';
    if(t>1000)
        t = 1000;

    for(i=0;i<t;i++)
        cout<<v[i]<<" ";
    return 0;
}