Cod sursa(job #1581350)

Utilizator Darius15Darius Pop Darius15 Data 26 ianuarie 2016 19:16:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,s1;
int n,m,k=0,pr[2000001],i,sol[2000001],l;
int main()
{
    f>>s>>s1;
    n=s.length();
    for (i=n;i>=1;i--)
      s[i]=s[i-1];
    m=s1.length();
    for (i=m;i>=1;i--)
      s1[i]=s1[i-1];
    pr[1]=0;
    for (i=2;i<=n;i++)
    {
      while (k && s[k+1]!=s[i])
        k=pr[k];
      if (s[k+1]==s[i])
        k++;
      pr[i]=k;
    }
    k=0;
    for (i=1;i<=m;i++)
    {
      while(k && s[k+1]!=s1[i])
        k=pr[k];
      if (s[k+1]==s1[i])
      k++;
      if (k==n)
      {
        k=pr[n];
        sol[++l]=i-n;
      }
    }
    g<<l<<'\n';
    for (i=1;i<=min(l,1000);i++)
      g<<sol[i]<<' ';
    return 0;
}