Cod sursa(job #2462166)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 26 septembrie 2019 20:47:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
using namespace std;

int v[2000005],ans[1005];
char s1[2000005],s2[2000005];

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int u,k=0,n,l,j;
    cin>>s1>>s2;
    u=strlen(s1);
    j=0;
    for(int i=1;i<u;i++)
    {
        while(s1[i]!=s1[j]&&j>0)
            j=v[j-1];
        if(s1[i]==s1[j])
            j++;
        v[i]=j;
    }
    n=u;
    u=strlen(s2);
    j=0;
    for(int i=0;i<u;i++)
    {
        while(s2[i]!=s1[j]&&j>0)
            j=v[j-1];
        if(s2[i]==s1[j])
            j++;
        l=j;
        if(l==n)
        {
            k++;
            if(k<=1000)
                ans[k]=i-n+1;
            l=0;
        }
    }
    cout<<k<<endl;
    for(int i=1;i<=min(1000,k);i++)
        cout<<ans[i]<<" ";
    return 0;
}