Cod sursa(job #2208757)

Utilizator andreeagoideaAndreea Goidea andreeagoidea Data 31 mai 2018 12:48:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

char a[2000001], b[2000001];
int pi[2000001], ans[2000001], s[1001];

int n, m, k, sol;

int minim(int a, int b)
{
    if(a<b)
        return a;
    return b;
}

int main()
{
    fin>>a;
    fin.get();
    fin>>b;
    n=strlen(a);
    m=strlen(b);
    for(int i=n;i>=1;i--)
        a[i]=a[i-1];
    for(int i=m;i>=1;i--)
        b[i]=b[i-1];
    a[0]='-';
    b[0]='.';
    for(int i=2; i<=n; i++)
    {
        while(k && a[k+1]!=a[i])
            k=pi[k];
        if(a[k+1]==a[i])
            k++;
        pi[i]=k;
    }
    k=0;
    for(int i=1; i<=m; i++)
    {
        while(k && a[k+1]!=b[i])
            k=pi[k];
        if(a[k+1]==b[i])
            k++;
        ans[i]=k;
        if(k==n)
        {
            sol++;
            if(sol<=1000)
                s[sol]=i-n;
            k=pi[n];
        }
    }
    fout<<sol<<"\n";
    for(int i=1; i<=minim(sol, 1000); i++)
            fout<<s[i]<<" ";
    return 0;
}