Cod sursa(job #2781690)

Utilizator alien14Razvan alien14 Data 10 octombrie 2021 11:24:16
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 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;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector<int>res;

void KMP(string a, string b)
{
    int n = b.length();
    int lps[n];
    lps[0] = 0;

    int i=0, j=1;

    while(j<n)
    {
        if(b[i] == b[j])
        {
            lps[j] = i+1;
            i++;j++;
        }
        else if(i==0)
        {
            lps[j] = 0;
            j++;
        }
        else i = lps[i-1];
    }

    int m = a.length();

    j=0,i=0;
    while(j<m || (j>=m && (j-i)<m))
    {
        if(b[i] == a[j%m])
        {
            j++;
            i++;
            if(i == n)
            {
                res.push_back(j-b.size());
            }
        }
        else if(i==0)
            j++;
        else i = lps[i-1];
    }
}

int main() 
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string a,b;
    fin>>a>>b;
    KMP(b,a);
    fout<<res.size()<<'\n';
    for(auto x: res)
        fout<<x<<" ";
    fin.close();
    fout.close();
    return 0;
}