Har suttit och klurat på det här ett tag nu men kan inte komma på en bra lösning.

Jag har 2 strängar med okänt innehåll, vad jag dock vet är att slutet av sträng 1 ibland kan matchas med början av sträng 2, om så är fallet så vill jag ta bort den matchande biten från sträng 1.


till exempel
string1 = "lite text som fortsätter";
string2 = "som fortsätter i string2";

I det här fallet vill jag att programmet ska identifiera "som fortsätter" och ta bort det från string1 så att slutresultatet är:
string1 = "lite text ";
string2 = "som fortsätter i string2";

Problemet är att jag inte vet längden på den matchande biten och den förekommer inte heller alltid.

Detta verkar fungera, men jag garanterar inte att det är helt buggfritt ;)

            string string1 = "lite text som fortsätter";
            string string2 = "som fortsätter i string2";

            int Pos = string1.Length;
            int MatchandePos = string1.Length;

            while (string1.Length - Pos < string2.Length)
            {
                Pos--;
                if (string2.StartsWith(string1.Substring(Pos)))
                    MatchandePos = Pos;
            }
            string1 = string1.Substring(0, MatchandePos);

Tack, den verkar fungera. Koden körs bara ungefär var 10e minut och textsträngen är runt 1000-2000 tecken så det går utmärkt.

Jag lade även in en else{ break; } i if-satsen så den slutar loopa när den inte hittar någon match längre.

Jag tyckte det var ett rätt kul problem så jag hakar på:

Bygger på samma princip som Johans men den jämför första o sista tecknet på ett index och om båda matchar så görs en full matchning.

static string GetOverlap(string string1, string string2)
{
    for (int index = 0; index < string1.Length && index < string2.Length; index++)
    {
        if (string2[0] == string1[string1.Length - 1 - index] &&
            string2[index] == string1[string1.Length - 1])
        {
            string possibleMatch = string2.Substring(0, index + 1);
            if (string1.EndsWith(possibleMatch))
                return possibleMatch;
        }
    }

    return null;
}

Hehe, var tvungen att göra en test för att se hur det blev i Linq :-)

static string GetOverlap(string string1, string string2)
{
    Func<int, bool> firstCharMatches = index => string2[0] == string1[string1.Length - 1 - index];
    Func<int, bool> lastCharMatches = index => string2[index] == string1[string1.Length - 1];

    var match =
        from index in Enumerable.Range(0, Math.Max(string1.Length, string2.Length))
        where firstCharMatches(index) && lastCharMatches(index)
        let possibleMatch = string2.Substring(0, index + 1)
        where string1.EndsWith(possibleMatch)
        select possibleMatch;

    return match.FirstOrDefault();
}

<b>Jag lade även in en else{ break; } i if-satsen så den slutar loopa när den inte hittar någon match längre.</b>

Jag har faktiskt redan tänkt på det, men då fungerar det inte när det finns flera möjliga träffar, som exempel (kom dock inte på något exempel med bra svenska...)


string1: Jag åt en potatis, sedan en
string2: en potatis, sedan en palsternacka

/Johan

Va dum man är, är ju mycket smartare att böra söka framifrån om man ändå bara vill ha första träffen...

            string string1 = "lite text som fortsätter";
            string string2 = "som fortsätter i string2";

            int Pos = 0;
            for (Pos = 0; Pos < string2.Length; Pos++)
            {
                if (string2.StartsWith(string1.Substring(Pos)))
                    break;

                Pos++;
            }
            string1 = string1.Substring(0, Pos);

Strängen är ju rätt lång så om man söker framifrån måste den ju loopa rätt många gånger så jag gillar din första lösning mera. Fick dock ändra den sista raden
<code>string1 = string1.Substring(0, Pos);</code>
till
<code>string1 = string1.Substring(0, string1.Length-Pos);</code>
eftersom den annars räknar Pos framifrån när den ju ska räkna bakifrån.


Just nu ser min kod ut såhär och verkar fungera, behöver dock göra lite mera testande.

<code> public string DeleteDuplicateText(string oldText, string newText){
int Pos = oldText.Length;
int MatchingPos = newText.Length;

while (oldText.Length - Pos < newText.Length)
{
Pos--;
if (newText.StartsWith(oldText.Substring(Pos)))
{
MatchingPos = Pos;
}
else
{
break;
}
}
oldText = oldText.Substring(0, oldText.Length - MatchingPos+1);
return(oldText);
}</code>


Så den loopar alltså igenom oldText (string1 i ditt exempel) bakifrån och om en match hittas testar den loopa igen ända tills den inte matchar längre. Matchingpos får ett värde för lågt eftersom den räknar ner i början av loopen vilket är anledningen att jag i sista raden skriver MatchingPos+1.

Nej du har rätt, nu var det jag som tänkte fel, din andra lösning verkar faktiskt bättre, ska testa den.

Varför inte bara:

        static string Check(string s1, string s2)
        {
            for (int i = 0; i < s2.Length; i++)
                if (s2.StartsWith(s1.Substring(i)))
                    return s1.Substring(0, i) + s2;

            return s1 + s2;
        }

Skulle vara roligt att se prestandan (i tid) på de olika lösningarna. Någon som har några mätningar?

Har benchmarkat lite, mitt exempel var 4 ggr snabbare än de andra.

Anledningen är att substring allokerar nya strängar och strängar tar tid att allokera.
min version använder bara substring när den tror att den hittat en match.

Dock är det rätt ointressant i verkligheten om man inte har tighta loopar som gör det här.
Om det som OP säger att det ska köras en ggr var 10e minut så spelar det 0 roll..

TestKoden:
(Med vissa ändringar eftersom de olika lösningarna som publicerats inte klippte korrekt)

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace MatchaSträng
{
    class Program
    {
        static void Main(string[] args)
        {
            string string1 = @"Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. ";
            string string2 = @"sunt in culpa qui officia deserunt mollit anim id est laborum. fobar kalle anka satt på en planka";

            string res = "";
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < 200000; i++)
            {
                res = Lösning1.Check(string1, string2);
            }
            sw.Stop();
            Console.WriteLine(res);
            Console.WriteLine(sw.Elapsed);
            Console.WriteLine();
            GC.Collect();

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 200000; i++)
            {
                res = Lösning2.Check(string1, string2);
            }
            sw.Stop();
            Console.WriteLine(res);
            Console.WriteLine(sw.Elapsed);
            Console.WriteLine();
            GC.Collect();


            sw.Reset();
            sw.Start();
            for (int i = 0; i < 200000; i++)
            {
                res = Lösning3.Check(string1, string2);
            }
            sw.Stop();
            Console.WriteLine(res);
            Console.WriteLine(sw.Elapsed);
            GC.Collect();

            Console.ReadLine();
        }
    }


    public class Lösning1
    {
        public static string Check(string s1, string s2)
        {
            for (int i = 0; i < s2.Length; i++)
                if (s2.StartsWith(s1.Substring(s1.Length - 1 - i)))
                    return s1.Substring(0, s1.Length - 1 - i);

            return s1;
        }
    }

    public class Lösning2
    {
        public static string Check(string oldText, string newText)
        {
            int Pos = oldText.Length;
            int MatchingPos = newText.Length;

            while (oldText.Length - Pos < newText.Length)
            {
                Pos--;
                if (newText.StartsWith(oldText.Substring(Pos)))
                {
                    MatchingPos = Pos;
                    break;
                }
                else
                {
                    continue;
                }
            }
            oldText = oldText.Substring(0, MatchingPos);
            return (oldText);

        }
    }

    public class Lösning3
    {
        public static string Check(string string1, string string2)
        {
            for (int index = 0; index < string1.Length && index < string2.Length; index++)
            {
                if (string2[0] == string1[string1.Length - 1 - index] &&
                    string2[index] == string1[string1.Length - 1])
                {
                    string possibleMatch = string2.Substring(0, index + 1);
                    if (string1.EndsWith(possibleMatch))
                        return string1.Substring (0,string1.Length - 1 - index);
                }
            }

            return string1;
        }
    }
}

Och ska vi snacka prestanda är det nog en modifierad variant av Boyer-Moore på låg nivå som är det starkaste kortet. Jag förutsätter att strängmatchningen i C# använder någon hyfsat smart algoritm, men det känns som att det finns något litet att vinna i att förstå exakt hur strängarna kan matchas i det här fallet.

Som Roger sa dock: helt oväsentligt i det här fallet.


/PS: Roger: Är du allvarlig när du använder svenska tecken i koden? Vik hädan!

>>/PS: Roger: Är du allvarlig när du använder svenska tecken i koden?

Använder du gamla kompilatorer som inte klarar sånnt? ;-)
Men nej, bara i demo cases.

>>C# använder någon hyfsat smart algoritm

Det är inte själva matchandet som är ett prestandaproblem utan garbage collectorn.
Strängar är immutable reference objekt i .net så det måste allokeras en ny sträng varje gång du klipper något med substring.

Jo, visst är det så att det inte spelar någon roll, men det är ändå kul att optimera! *besatt*

Jag använder DateTime.Now.Ticks för mina mätningar, men Stopwatch såg riktigt trevlig ut!

Stopwatch är riktigt trevlig att ha att göra med ;)

och så här gör man lite quick and dirty , förutsatt att det alltid är samma slut s1 som början på s2 :)

string reusult = string1.Substring(0, string1.LastIndexOf(string2.Substring(0,string2.IndexOf(' '))));

Kommer inte funka, dels om första strängen slutar med
"a b c tysk"

och andra är
"tysk-talande d e f"


Dels om första slutar med

"a b c tysk tysk"

och andra börjar med

"tysk tysk d e f"

som jag sa den är ju dirty , funkade fint me rogers test strängar :)

det jag ville påvisa är att det finns färdiga sökmetoder man kan använda i stället för loopar

Men det finns det (väl?) inte i det här fallet, såvida du inte tittar på någon slags greedy regular expressions.

Jag tror fortfarande att det snabbaste sättet är att helt gå ifrån substrings och istället arbeta med någon variant av Boyer-Moore (ett träd istället för ena tabellen?).

>>ett träd istället för ena tabellen

Du får ju räkna in tiden att sammanställa trädet också.
Så det blir väl någon form av break even gräns på storleken av strängarna som matchas.
Tex om du har stora strängar men väldigt små överlappningar så bör ju BM fungera dåligt då det blir mycket lookupbyggande och lite matchande.

Jo, förstås. Boyer-Moore är ju tämligen meningslös om man har ett pattern på 2 tecken.

Börjar fundera lite på om binärsökning inte kan vara en bra grej också. Typ först bygga upp ett index över första positionen för alla tecken på högra strängen, sen köra något i stil med

left = 0;
right= s1.size()-1;
while (left != right){ //med lite försiktighet här förstås
middle = (right + left)/2;
//kolla om början av strängen måste vara till höger eller vänster
}

Där kommentaren blir något i stil med att kolla om det är teoretiskt möjligt att s1[middle] och framåt är med i början. Känner att det borde gå, men har inget mer specifikt att leverera.