Cod sursa(job #2194670)

Utilizator bpalaniciPalanici Bogdan bpalanici Data 14 aprilie 2018 00:20:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>

using namespace std;
int t[2000005],m,n,sol[1003],poz;
int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string s,s1;
    fin>>s>>s1;
    m=s.size(); n=s1.size();
    int i,j,a,b,k=0;
    for (i=1;i<m;i++)
    {
        while (k>0 && s[i]!=s[k]) k=t[k-1];
        if (s[i]==s[k]) k++;
        t[i]=k;
    }
    k=0;
    for (i=0;i<n ;i++)
    {
        while (k>0 && s[k]!=s1[i]) k=t[k-1];
        if (s[k]==s1[i]) k++;
        if (k==m)
        {
            poz++;
            if (poz<=1000) sol[poz]=i-k+1;
            k=t[k-1];
        }
    }
    fout<<poz<<"\n";
    poz=min(poz,1000);
    for (i=1;i<=poz;i++)
        fout<<sol[i]<<" ";
    return 0;
}