Pagini recente » Cod sursa (job #857050) | Cod sursa (job #2182298) | Cod sursa (job #1706430) | Cod sursa (job #2223262) | Cod sursa (job #2097046)
#include <bits/stdc++.h>
#define MAX 2000000
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char A[MAX+5],B[MAX+5];
int n,m;
int LPS[MAX+5];
vector <int> V;
void citire(void)
{
fi>>A;
fi>>B;
n=strlen(B);
m=strlen(A);
}
void generare_lps(char P[])
{
/// calculeaza lungimile prefixelor care sunt si sufixe
LPS[0]=0;
for(int i=1,j=0; i<m;)
{
if(P[i]==P[j])
{
LPS[i]=j+1;
i++;
j++;
}
else
{
if(j==0)
{
LPS[i]=0;
i++;
}
else
j=LPS[j-1];
}
}
}
void KMP(char T[], char P[])
{
for(int i=0,j=0; i<n;)
{
if(T[i]==P[j])
{
i++;
j++;
}
if(j==m)
{
if(V.size()<1000)
V.push_back(i-m);
j=LPS[j-1];
}
else
if(i<n && T[i]!=P[j])
{
if(j!=0)
j=LPS[j-1];
else
i++;
}
}
}
void afisare(void)
{
fo<<V.size()<<"\n";
for(int i=0; i<V.size(); i++)
fo<<V[i]<<" ";
}
int main()
{
citire();
generare_lps(A);
KMP(B,A);
afisare();
fi.close();
fo.close();
return 0;
}