Cod sursa(job #2781702)

Utilizator alien14Razvan alien14 Data 10 octombrie 2021 11:40:47
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;


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);
    int l = 0;
    if(res.size() > 1000)
        l = 1001;
    else l = res.size();
    fout<<l<<'\n';

    for(int i=0;i<l;i++)
        fout<<res[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}