Pagini recente » Cod sursa (job #1738103) | Cod sursa (job #1974445) | Cod sursa (job #1475360) | Cod sursa (job #2831372) | Cod sursa (job #1667751)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i, j, q, pref[2000005], q2, gasite, poz[2000005];
char v[2000005], t[2000005];
int main()
{
fin.getline(v, 2000005);
q = strlen(v);
fin.getline(t, 2000005);
q2 = strlen(t);
j = 0;
pref[0] = 0;
for(i=1; i <= q; i++)
{
if(v[i] == v[j])
{
pref[i] = pref[i-1]+1;
j++;
}
else
{
while(v[j] != v[i] && j != 0)
{
j = pref[j-1];
}
}
}
j = 0;
for(i=0; i < q2; i++)
{
if(t[i] == v[j])
{
j++;
}
else
{
if(j != 0)
j = pref[j-1];
}
if(j == q)
{
gasite++;
poz[gasite] = i-q+1;
j=pref[j-1];
}
}
fout << gasite << '\n';
for(i=1; i <= gasite; i++)
fout << poz[i] << ' ';
}