Cod sursa(job #1069216)

Utilizator mikeshadowIon Complot mikeshadow Data 29 decembrie 2013 16:32:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)
 
#define INF 10000000000001
 
using namespace std;


#ifndef TEST
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif
 
#define MAXN 2000000
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pp;

string s,t;
 
vector<int> sol;
 
int T[MAXN+1];
 
void build()
{
    int c = 0;
    T[0] = -1;
    T[1] = 0;
    for (int i=2; i<s.length(); i++)
    {
        if (s[i-1]==s[c])
        {
            c++;
            T[i]=c;
        } else if (c>0)
        {
            c = T[c];
            i--;
        } else T[i]=0;
    }
}
 
int main()
{
    fin>>s>>t;
 
    int sl,tl;
    sl = s.length();
    tl = t.length();
 
    build();
 
    int c=0,i=0;
    while (i+sl <= tl)
    {
        if (t[i+c]==s[c])
        {
            if (c==sl-1)
            {
                sol.push_back(i);
                i =i+c- T[c];
                if (T[c]>-1)
                c = T[c];
                else c=0;
            }
            else c++;
        } else
        {
            i = i+c -T[c];
            if (T[c]>-1)
                c = T[c];
            else c=0;
        }
    }
 
    fout<<sol.size();
    fout<<'\n';
 
    for (int i=0; i<min(sol.size(),1000); i++)
        fout<<sol[i]<<' ';
    return 0;
}