Cod sursa(job #2412044)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 21 aprilie 2019 16:30:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda qsasdasgegs Marime 0.85 kb
#include<bits/stdc++.h>
using namespace std;

const int maxN=(2e6)+5;

char s[maxN],p[maxN];
int pref[maxN];
vector<int> sol;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);


    scanf("%s",s+1);

    scanf("\n");

    scanf("%s",p+1);

    int k=0;

    int n=strlen(s+1);
    int m=strlen(p+1);

    for(int i=2;i<=n;i++)
    {
        while(k && s[k+1]!=s[i]) k=pref[k];
        if(s[k+1]==s[i]) k++;
        pref[i]=k;
    }

    k=0;
    int sz=0;

    for(int i=1;i<=m;i++)
    {
        while(k && s[k+1]!=p[i]) k=pref[k];
        if(s[k+1]==p[i]) k++;
        if(k>=n)
        {
            sz++;
            if(sz<=1000) sol.push_back(i-n);
        }
    }

    printf("%d\n",sz);

    for(auto it:sol)
        printf("%d ",it);

    printf("\n");

    return 0;
}